M. Function and Function
队友说直接暴力即可
#include <cmath> #include <cstdio> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; int get(int x) { if (x == 0) return 1; int sum = 0; while (x) { int d = x % 10; x /= 10; if (d == 0 || d == 4 || d == 6 || d == 9) sum += 1; else if (d == 8) sum += 2; } return sum; } int main() { int t; scanf("%d", &t); while (t--) { int x, k; scanf("%d%d", &x, &k); int res; if (k == 0) { res = x; printf("%d\n", res); continue; } while (k--) { x = get(x); res = x; if (x == 1) { if (k % 2 == 0) { res = 1; } else res = 0; break; } } printf("%d\n", res); } return 0; }
C.
const int maxn=1e6+7; int T,n,a[maxn],b[maxn],f; char x[maxn],y[maxn]; ll sum; int main(){ T=read(); while(T--){ n=read(); scanf("%s%s",x,y); f=0; for(int i=0;i<n;i++){ a[i+1]=x[i]-'0'; b[i+1]=y[i]-'0'; if(a[i]==b[i]&&a[i+1]!=b[i+1]) f++; } if(n==1){ if(a[1]!=b[1]) sum=0; else sum=1; out(sum); putchar('\n'); continue; } if(f==0) sum=1ll*n*(n+1)/2; else if(f==1) sum=(n-1)*2; else if(f==2) sum=6; else sum=0; out(sum); putchar('\n'); } }
Plants vs. Zombies
二分答案
在处理的过程中直接在下一个和当前位置左右横跳即可
#define Clear(x,val) memset(x,val,sizeof x) ll a[maxn]; ll nowCnt[maxn],needCnt[maxn]; ll n,m; bool check(ll mid) { if(mid == 0LL) return true; for(int i=1; i<=n; i++) { nowCnt[i] = 0; needCnt[i] = (mid - 1) / a[i] + 1; } for(int i=1; i<=n; i++) { if(n == i && nowCnt[i] >= needCnt[i]) return true; /** if(nowCnt[i] >= needCnt[i]) { if(i == n) return true; // continue; } **/ if(m <= 0) return false; ++ nowCnt[i]; -- m; if(nowCnt[i] >= needCnt[i]) continue;/// already okay ///else: ll stillNeed = needCnt[i] - nowCnt[i]; if(stillNeed*2 > m) return false; m -= 2 * stillNeed; nowCnt[i+1] += stillNeed;/// * 2 /** cur_pos + 1 **/ } return true; } int main() { int _ = read; while (_ --) { n = read,m = read; ll tm = m; ll mini = 0x3f3f3f3f; for(int i=1; i<=n; i++) { a[i] = read; mini = min(mini,a[i]); } // /** if(m == 0) { puts("0"); } else if(m < n) { puts("0"); } else if(m == n) { printf("%lld\n",mini); } else { // **/ ll l = 0,r = 1e17 + 1; while(l < r) { ll mid = l + r + 1>> 1; m = tm; if(check(mid)) l = mid; else r = mid - 1; } printf("%lld\n",l); } } return 0; } /** 2 4 8 3 2 6 6 3 9 10 10 1 **/
J . Books
二分了好久发现不是二分，比较考验思维
附带几组hack 数据样例
int a[maxn]; vector<int> vet; int main() { int _ = read; while (_ --) { int n = read,m = read; int cnt = 0; vet.clear(); vet.push_back(0); int zero = 0; for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); if (a[i] == 0) zero++; else vet.push_back(a[i]); } if (zero > m) { puts("Impossible"); continue; } if (n == m) { puts("Richman"); continue; } int mini = 0x3f3f3f3f; int siz = vet.size() - 1; m -= zero; ll ans = 0; int select = 0; for(int i=1; i<=siz; i++) { ++ select; if(select <= m) { ans += vet[i]; } else { mini = min(mini,vet[i]); } } // cout << ans << endl; // cout << mini << endl; ans += mini - 1; // cout << ans << endl; printf("%lld\n",ans); } return 0; } /** 2 1 5 4 0 0 0 0 1 1 10 3 100000 100000 100000 1 1 1 1 1 1 1 1 10 6 10000 1 1 1 1 1 1 1 10000 10000 4 4 2 1 2 4 8 4 0 100 99 98 97 2 2 10000 10000 5 3 0 0 0 0 1 **/
I. Soldier Game
三维线段树
typedef pair<int,int> pll; const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3f; const LL mod = (int)1e9+7; const int N = 1e5 + 100; int a[N][2]; pll p[N<<1]; bool cmp(pll & x, pll & y){ return a[x.fi][x.se] < a[y.fi][y.se]; } int tree[N<<2][2][2]; void Build(int l, int r, int rt){ tree[rt][0][0] = tree[rt][0][1] = tree[rt][1][0] = tree[rt][1][1] = 0; if(l == r) { tree[rt][1][0] = 1; return ; } int m = l+r >> 1; Build(lson); Build(rson); } void PushUp(int rt){ tree[rt][0][0] = (tree[rt<<1][0][0] && tree[rt<<1|1][0][0]) || (tree[rt<<1][0][1] && tree[rt<<1|1][1][0]); tree[rt][0][1] = (tree[rt<<1][0][0] && tree[rt<<1|1][0][1]) || (tree[rt<<1][0][1] && tree[rt<<1|1][1][1]); tree[rt][1][0] = (tree[rt<<1][1][0] && tree[rt<<1|1][0][0]) || (tree[rt<<1][1][1] && tree[rt<<1|1][1][0]); tree[rt][1][1] = (tree[rt<<1][1][1] && tree[rt<<1|1][1][1]) || (tree[rt<<1][1][0] && tree[rt<<1|1][0][1]); } void Update(int L, int op,int l, int r, int rt){ if(l == r){ tree[rt][0][op] ^= 1; return ; } int m = l+r >> 1; if(L <= m) Update(L, op, lson); else Update(L, op, rson); PushUp(rt); } int main(){ int T, n; scanf("%d", &T); while(T--){ scanf("%d", &n); int m = 0; for(int i = 1; i <= n; ++i){ scanf("%d", &a[i][0]); p[++m] = pll(i,0); if(i-1) { a[i-1][1] = a[i-1][0] + a[i][0]; p[++m] = pll(i-1,1); } } sort(p+1, p+1+m, cmp); Build(1,n,1); LL ans = INF; for(int i = 1, j=1; i <= m; ++i){ while(j <= m && !tree[1][0][0]){ Update(p[j].fi, p[j].se, 1, n, 1); j++; } if(tree[1][0][0]) ans = min(ans, 1ll*a[p[j-1].fi][p[j-1].se] - a[p[i].fi][p[i].se]); Update(p[i].fi, p[i].se, 1, n, 1); } printf("%lld\n", ans); } return 0; }
