T1
区间筛裸题
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e6+10; int pri[N]; ll num[N];//FOR [L, R] bool npri[N]; ll l, r; void sieve(int len){ for(int i = 2; i <= len; ++i){ if(!npri[i]) pri[++pri[0]] = i; for(int j = 1; j <= pri[0] && i * pri[j] <= len; ++j){ npri[i * pri[j]] = true; if(i % pri[j] == 0) break; } } for(int i = 1; i <= pri[0]; ++i){ for(ll j = ceil(1.0 * l/pri[i]); j <= floor(1.0 * r/pri[i]); ++j){ assert(j * pri[i] >= l && j * pri[i] <= r); if(!num[j * pri[i] - l + 1]) num[j * pri[i] - l+1] = pri[i]; } } } signed main(){ ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> l >> r; sieve(1e6 + 5); for(int i = 1; i<= r -l + 1; ++i){ if(!num[i]) num[i] = i + l - 1; cout <<num[i] <<"\n"; } return 0; }
T2
纯模拟,打挂了一个点:检查可行性后复原时不是复原的原值而是0
100->70
#include<bits/stdc++.h> using namespace std; const int N = 15, Q = 100 + 10, L = 50; enum{acc = 1, err_spa, err_row, err_col, err_sqr}; typedef pair<int, int> pii; vector<pii> blk[N]; int bel[N][N]; int n = 9; struct t_block{ int data[N][N]; static bool legal(int x){ return 1 <= x && x <= 9; } int check_simp(int x, int y, int p){ bool vis[N] = {}; if(legal(data[x][y])) return err_spa; data[x][y] = p; for(int i = 1; i <= n; ++i){ if(!legal(data[x][i])) continue; if(vis[data[x][i]]) return err_row; vis[data[x][i]] = true; } memset(vis, 0, sizeof(vis)); for(int i = 1; i <= n; ++i){ if(!legal(data[i][y])) continue; if(vis[data[i][y]]) return err_col; vis[data[i][y]] = true; } memset(vis, 0, sizeof(vis)); for(auto plc : blk[bel[x][y]]){ if(!legal(data[plc.first][plc.second])) continue; if(vis[data[plc.first][plc.second]]) return err_sqr; vis[data[plc.first][plc.second]] = true; } return acc; } int check(int x, int y, int p){ int rw = data[x][y]; int ret = check_simp(x, y, p); data[x][y] = rw; return ret; } int insert(int x, int y, int p){ int ret = check(x, y, p); if(ret != acc) return ret; data[x][y] = p; return acc; } int del(int x, int y){ if(!legal(data[x][y])) return err_spa; data[x][y] = 0; return acc; } vector<int> query(int x, int y){ vector<int> ret; if(data[x][y]) return {-1}; for(int i = 1; i <= 9; ++i){ if(check(x, y, i) == acc) ret.push_back(i); } return ret; } const int* operator[](int x)const{ return data[x]; } pii merge(const t_block & a, const t_block& b){ int ret1 = 0, ret2 = 0; for(int i = 1; i <= n; ++i){ for(int j = 1; j <= n; ++j){ if(a[i][j] && check(i, j, a[i][j])){ ++ret1; data[i][j] = a[i][j]; }else if(b[i][j] && check(i, j, b[i][j])){ ++ret2; data[i][j] = b[i][j]; } } } return {ret1, ret2}; } void showline(){ for(int i = 1; i <= 9; i) cout <<"+-"; cout <<"+\n"; } void show(){ for(int i = 1; i <= n; ++i){ showline(); for(int j = 1; j <= n; ++j){ cout <<"|" << data[i][j]; } cout <<"|"<<"\n"; } showline(); } void input(){ char str[L]; for(int i = 1; i <= n; ++i){ cin >> (str + 1); cin >> (str + 1); for(int j = 1; j <= n; ++j){ data[i][j] = str[j * 2] -'0'; } } cin >> (str + 1); } }block[Q]; int main(){ for(int i = 1; i <= 9; ++i){ for(int j = 1; j <= 9; ++j){ bel[i][j] = ceil(1.0 * i / 3) * 3 + ceil(1.0 * j / 3); } } for(int i = 1; i <= 9; ++i){ for(int j = 1; j <= 9; ++j){ blk[bel[i][j]].emplace_back(i, j); } } block[0].input(); int q; cin >> q; for(int i = 1; i <= q; ++i){ char opt[L]; cin >> (opt + 1); if(opt[1] == 'I'){ block[i] = block[i-1]; int x, y, p; cin >> x >> y >> p; int ret = block[i].insert(x, y, p); switch(ret){ case acc: cout <<"OK!"<<"\n";break; case err_spa: cout<<"Error!"<<"\n";break; case err_row: cout <<"Error:row!"<<"\n";break; case err_col: cout<<"Error:column!"<<"\n";break; case err_sqr: cout<<"Error:square!"<<"\n";break; default: abort(); } }else if(opt[1] == 'D'){ int x, y; cin >> x >> y; block[i] = block[i-1]; int ret = block[i].del(x, y); if(ret == err_spa){ cout <<"Error!"<<"\n"; }else if(ret == acc){ cout<<"OK!"<<"\n"; }else abort(); }else if(opt[1] =='Q'){ int x, y; cin >> x >> y; block[i] = block[i-1]; vector<int> p = block[i].query(x, y); if(p.size() == 1 && p[0] == -1){ cout <<"Error!"<<"\n"; }else{ cout << p.size() <<"\n"; for(int j : p){ cout << j <<"\n"; } } }else if(opt[1] =='M'){ int a, b; cin >> a >> b; pii res = block[i].merge(block[a], block[b]); cout << res.first <<" " << res.second <<"\n"; }else if(opt[1] == 'P'){ block[i] = block[i-1]; block[i].show(); } } return 0; }
T3
结论题, 思路大概就是设a位矩阵第一行,b为矩阵第二行,然后答案即为左上角Z字形走到右下角的max,交换两项的判断条件满足传递性,所以可以拓展,直接sort即可
#pragma GCC optimize(3) #pragma GCC optimize("Ofast") #include<bits/stdc++.h> using namespace std; const int N = 1e5; typedef long long ll; const ll INF = 0x3f3f3f3f3f3f3f3f; struct stu{ int a, b; bool operator <(const stu& rhs)const{ return min(a, rhs.b) < min(rhs.a, b); } }s[N]; ll c[N]; int n; ll get_ans(){ ll res = 0; c[1] = s[1].a + s[1].b; ll sa = s[1].a; for(int i = 2; i <= n; ++i){ sa += s[i].a; c[i] = max(c[i-1], sa) + s[i].b; } for(int i = 1; i <= n; ++i){ res = max(res, c[i]); } return res; } void solve(){ cin >> n; for(int i = 1; i <= n; ++i) cin >> s[i].a >> s[i].b; sort(s + 1, s + 1 + n); cout << get_ans() <<"\n"; } int main(){ int T; ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> T; while(T--){ solve(); } return 0; }
T4
第一部分:直接概率计算,打挂了输出格式:50->10
第二部分:类数位dp
设\(f(x)\)为与\(x\) xor后最大值的操作数
我们发现先考虑填入最高位,若x填1,则f(x)填0,此时x有限制,f(x)无限制,所以后几位均为1,此时可以直接计算
此时\(x\)无限制,\(f(x)\)有限制,我们只针对这种情况进行dfs
若\(n-1\)此时为\(1\), 则\(x = 0\)时,\(f(x) = 1\), \(x = 1\)时,\(f(x) = 0\)
针对第一种情况,\(f(x)\)仍有限制,我们直接dfs即可,第二种情况,均无限制,直接计算
若\(n-1\)此时为\(0\), 则\(f(x)\)必然为\(0\),且有限制,所以只能继续dfs
log有精度误差,慎用
#include<bits/stdc++.h> #define int ll using namespace std; typedef long long ll; typedef long double ld; typedef pair<ld, ld> pdd;//概率 ll n;ld p; ll get_cnt(int d){ ll res1 = floor(1.0 * (n + 1) / (1ll << (d +1))) *(1ll << d); ll res2 = ((n+1) % (1ll << (d + 1))) - (1ll << (d)); return res1 + max(res2, 0ll); } const ld eps =1e-10; ld mabs(ld x){ return x > 0? x : -x; } ld equal(ld x, ld y){ return mabs(x-y) <= eps; } void print(ld x){ if(equal(x, 0)){ assert(0); cout<<fixed<<setprecision(5) << x <<" " << 0 << endl; return; } int bits = log10(x); x = x * pow(10, -bits); cout<<fixed<<setprecision(5) << x <<" " << bits << endl; } ll getpos(int x){ return (n >> x) & 1; } ld dfs(int pos, bool lim){//限制f(x) if(pos < 0) return 0; ld res = 0; if(lim){//第一位,限制x, 也限制f(x) if(getpos(pos) == 1){ //取1, 则f(x)取0,然后f(x)不限制 res = res + 1.0 * (((n) &((1ll << pos) - 1)) + 1) / (n + 1) * ((1ll << (pos + 1)) -1); //取0,则f(x)取1 res = res + 1.0 * (1ll << (pos)) / (n + 1) * (1ll << pos); res = res + dfs(pos - 1, false);//x不限制,但是f(x)限制 } else res=dfs(pos-1,1); }else{//只限制f(x) if(getpos(pos) == 1){ //填1, 则f(x)填0, 接下来都不限制 res = res + 1.0 * (1ll << pos) / (n + 1)* ((1ll << (pos + 1) )- 1); //填0, 则f(x)填1, 接下来限制f(x) res = res + 1.0 *(1ll << pos) / (n + 1)* (1ll << pos); res = res + dfs(pos - 1, false); }else{ //x 填1或0,f(x)只能填0,并且限制下去 //填1时,有贡献 res = res + 1.0 * (1ll << pos) /(n + 1) *(1ll << pos) + 2 * dfs(pos-1, false); } } return res; } signed main(){ ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> n >> p; cerr<<n << " " << p << endl; --n; int b = floor(log2(n)); ld ans1 = 0, ans2 = 0; for(int i = 0; i <= b; ++i){ ld prob = 1.0 * get_cnt(i) / (n+1); ld dt = 2 * prob *(1 - prob)* (1ll << i); ans2 = ans2 + dt; } ans1 = dfs(b, true); cerr<<"ans1 = "<<ans1 <<" ans2 = " <<ans2 << endl; ld ans = ans1 * p + ans2 * (1 - p); print(ans); return 0; }