赛时rank 47,T1 100,T2 0,T3 0,T4 20
做题策略不好,没做T2,死在T4上了。
感觉赛时就是唐。
T1 黑客
考虑枚举结果,如果存在贡献,那么一定有\(i+j=k\& gcd(i,j)=1\),统计一下有多少组即可
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
using ll = long long;using ull = unsigned long long;
using db = double;using ldb = long double;
#ifdef LOCAL
FILE *InFile = freopen("in.in","r",stdin),*OutFile = freopen("out.out","w",stdout);
FILE *ErrFile = freopen("err.err","w",stderr);
#else
FILE *InFile = stdin,*OutFile = stdout;
// FILE *ErrFile = freopen("err.err","w",stderr);
#endif
bool Cin = cin.tie(nullptr)->sync_with_stdio(false);
bool Cout = cout.tie(nullptr)->sync_with_stdio(false);
#define int long long
const int mod = 1e9 + 7;
ll a,b,c,d;
int f[1000];
signed main(){
cin>>a>>b>>c>>d;
for(int k = 1;k <= 999; ++k){
for(int i = 1;i < k; ++i){
int j = k - i;
if(__gcd(i,j) == 1){
ll up1 = b/i,up2 = d/j;
ll down1 = (a-1)/i,down2 = (c-1)/j;
// cerr<<i<<' '<<j<<' '<<min(max(up1-down2,0ll),max(up2-down1,0ll))<<'\n';
f[k] = (0ll + f[k] + min({max(up1-down2,0ll),max(up2-down1,0ll),max(up1-down1,0ll),max(up2-down2,0ll)}))%mod;
}
}
}
ll ans = 0;
for(int k = 1;k <= 999; ++k)
ans = (ans + 1ll*f[k]*k%mod)%mod;
cout<<ans;
}
T2 密码技术
考虑到无论如何排列都无影响,那么就考虑行和列分开。
将可以互相交换的放入一组,并查集维护,求连通块大小的阶乘。
行列贡献相乘
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
using ll = long long;using ull = unsigned long long;
using db = double;using ldb = long double;
#ifdef LOCAL
FILE *InFile = freopen("in.in","r",stdin),*OutFile = freopen("out.out","w",stdout);
// FILE *ErrFile = freopen("err.err","w",stderr);
#else
FILE *InFile = stdin,*OutFile = stdout;
// FILE *ErrFile = freopen("err.err","w",stderr);
#endif
bool Cin = cin.tie(nullptr)->sync_with_stdio(false);
bool Cout = cout.tie(nullptr)->sync_with_stdio(false);
const int N = 51,mod = 998244353;
int n,k;
int a[N][N],sum1[N],sum2[N],fa[N],siz[N];
int get_fa(int x){return (x == fa[x]?x:fa[x] = get_fa(fa[x]));}
signed main(){
cin>>n>>k;
for(int i = 1;i <= n; ++i) for(int j = 1;j <= n; ++j) cin>>a[i][j];
ll ans1 = 0;
for(int i = 1;i <= n; ++i) fa[i] = i,siz[i] = 1;
for(int i = 1;i <= n; ++i){
for(int j = 1;j < i; ++j){
bool flag = true;
for(int t = 1;t <= n; ++t){
if(a[i][t] + a[j][t] > k){flag = false;break;}
}
if(flag){
int fx = get_fa(i),fy = get_fa(j);
if(fx == fy) continue;
fa[fx] = fy;
siz[fy] += siz[fx];
get_fa(fx);
}
}
}
// for(int i = 1;i <= n; ++i) cerr<<siz[i]<<' ';
// cerr<<'\n';
ll ans = 1;
for(int i = 1;i <= n; ++i) {
if(fa[i] == i){
for(int j = siz[i];j >= 1; --j) ans = ans * j % mod;
}
}
for(int i = 1;i <= n; ++i) fa[i] = i,siz[i] = 1;
for(int i = 1;i <= n; ++i){
for(int j = 1;j < i; ++j){
bool flag = true;
for(int t = 1;t <= n; ++t){
if(a[t][i] + a[t][j] > k){flag = false;break;}
}
if(flag){
int fx = get_fa(i),fy = get_fa(j);
if(fx == fy) continue;
fa[fx] = fy;
siz[fy] += siz[fx];
}
}
}
for(int i = 1;i <= n; ++i) {
if(fa[i] == i){
for(int j = siz[i];j >= 1; --j) ans = ans * j % mod;
}
}
cout<<ans;
}
T3 修水管
发现期望难以转移,于是考虑先处理概率\(g\)
我们有\(ans=\sum_{i=1}^ng_id_i\)
如果一段水管被修复过,那么要么让它之前被修复,要么它没有炸掉。
设\(f_{i,j}\)表示在前\(i\)个位置,在\(r\)轮中修复过\(j\)次的期望。
\[f_{i,j}=f_{i-1,j}\times(1-p_i)^{r-j}+f_{i-1,j-1}\times(1-(1-p_i)^{r-j+1}) \]\[g_i=\sum_{j=0}^rf_{i-1,j}\times (1-(1-p_i)^{r-j}) \]点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
bool StdIn = cin.tie(nullptr)->sync_with_stdio(false);
bool StdOut = cout.tie(nullptr)->sync_with_stdio(false);
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 300;
db f[N][N],g[N],p[N];
int n,d[N],r;
signed main(){
int T;cin>>T;
while(T--){
cin>>n>>r;
for(int i = 1;i <= n; ++i) cin>>p[i]>>d[i];
memset(f,0,sizeof f);memset(g,0,sizeof g);
f[0][0] = 1;
for(int i = 1;i <= n; ++i){
for(int j = 0;j <= r; ++j){
f[i][j] = f[i-1][j] * pow(1-p[i],r-j);
if(j) f[i][j] += f[i-1][j-1]*(1-pow(1-p[i],r-j+1));
}
}
for(int i = 1;i <= n; ++i)
for(int j = 0;j <= r; ++j)
g[i] += f[i-1][j]*(1-pow(1-p[i],r-j));
db ans = 0;
for(int i = 1;i <= n; ++i) ans += g[i]*d[i];
cout<<fixed<<setprecision(10)<<ans<<'\n';
}
}
T4 货物搬运
deque/vector+分块
暴力删,暴力跑即可
这么简单的题我场上没切真是唐!
时间复杂度单次操作\(O(\sqrt {n})\)
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
using ll = long long;using ull = unsigned long long;
using db = double;using ldb = long double;
#ifdef LOCAL
FILE *InFile = freopen("in.in","r",stdin),*OutFile = freopen("out.out","w",stdout);
// FILE *ErrFile = freopen("err.err","w",stderr);
#else
FILE *InFile = stdin,*OutFile = stdout;
// FILE *ErrFile = freopen("err.err","w",stderr);
#endif
bool Cin = cin.tie(nullptr)->sync_with_stdio(false);
bool Cout = cout.tie(nullptr)->sync_with_stdio(false);
const int N = 1e5+10,M = sqrt(N)+10;
int n,q,a[N],pos[N],L[N],R[N],siz,lastans;
deque<int> Q[320];
int sum[320][N];
signed main(){
cin>>n;
for(int i = 1;i <= n; ++i) cin>>a[i];
siz = sqrt(n);
for(int i = 1;i <= siz; ++i) L[i] = R[i-1]+1,R[i] = i * siz;
if(R[siz] < n) siz++,L[siz] = R[siz-1]+1,R[siz] = n;
for(int i = 1;i <= siz; ++i){
for(int j = L[i];j <= R[i]; ++j){
pos[j] = i;
Q[i].push_back(a[j]);
sum[i][a[j]]++;
}
}
cin>>q;
int tot = 0;
while(q--){
int op,l,r,k;
cin>>op>>l>>r;
l = (l+lastans-1)%n+1;
r = (r+lastans-1)%n+1;
if(l > r) swap(l,r);
if(op == 1){
int p = pos[r],p1 = pos[l];
int x = *(Q[p].begin()+(r-L[p]));
sum[p][x]--;
Q[p].erase(Q[p].begin()+(r-L[p]));
if(l == L[p1]) Q[p1].push_front(x);
else Q[p1].insert(Q[p1].begin()+(l-L[p1]),x);
sum[p1][x]++;
for(int i = p1 + 1; i <= p; ++i){
int x = Q[i-1].back();
Q[i].push_front(x);
sum[i][x]++;sum[i-1][x]--;
Q[i-1].pop_back();
}
}
else{
tot++;
cin>>k;k = (k + lastans - 1) % n + 1;
int p = pos[l],q = pos[r],res = 0;
if(p == q){
for(int i = l;i <= r; ++i)
res += (Q[p][i-L[p]] == k);
}
else{
for(int i = p + 1;i < q; ++i) res += sum[i][k];
for(int i = l;i <= R[p]; ++i)
res += (Q[p][i-L[p]] == k);
for(int i = L[q];i <= r; ++i)
res += (Q[q][i-L[q]] == k);
}
cout<<(lastans = res)<<'\n';
}
}
}
总结一下吧,毕竟这么唐。
这两天的状态不是很好,集训时间太久了。
休息也没休息好。
打的很难评,赛时怎么也想不出正解,赛后才明白自己场上有多唐。
思维上还是有遗漏,对数学题总是有一种畏惧的心理,怎么想也想不出来。
一些简单题也会因此受影响。
读假题的现象时有发生,比如T2就没有把题读完。然后就似了。
菜是原罪。
马上就要放假了,调整一下,等再回来的时候应该就好了,应该吧……
标签:12,freopen,err,int,long,集训,FILE,using,csp From: https://www.cnblogs.com/hzoi-Cu/p/18334897