Codecraft-18 and Codeforces Round #458
C. Travelling Salesman and Special Numbers
题意： 一个由0、1 组成的数 n，操作：n 有 m 个 1，就把 n 变为 m。 问 <=n 的数中有多少个恰好经过 k 次操作能变为 1。
tags： dp[i][j] 表示长度为 i 且有 j 个 1 的串，比对应的 n 要小的方案数。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i<=b; ++i) #define per(i,b,a) for (int i=b; i>=a; --i) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second typedef long long ll; const int N = 1005, mod = 1e9+7; ll k, ans1[N], cnt, len; char s[N]; ll get(int x) { ll sum = 0; while(x) { if(x&1) ++sum; x >>= 1; } return sum; } ll dp[N][N], C[N][N]; void Init() { C[1][0] = C[1][1] = 1; rep(i,2,N-1) { C[i][0] = 1; rep(j,1,N-1) C[i][j] = (C[i-1][j] + C[i-1][j-1])%mod; } if(s[len]=='1') dp[len][1]=dp[len][0]=1; else dp[len][1]=0, dp[len][0]=1; per(i,len-1,1) { dp[i][0]=1; per(j,len-i+1,1) { if(s[i]=='1') dp[i][j] = (dp[i+1][j-1]+C[len-i][j])%mod; else dp[i][j] = dp[i+1][j]; } } } int main() { scanf("%s%lld", s+1, &k); len = strlen(s+1); ll tmp, cnt=0, ans=0; rep(i,1,len) if(s[i]=='1') ++cnt; Init(); rep(i,1,1000) { tmp = get(i); if(i==1) ans1[i] = 0; else ans1[i] = ans1[tmp]+1; if(ans1[i]==k-1) ( ans += dp[1][i]%mod ) % mod; } if(k==0) ans = 1; if(k==1) ans = len-1; printf("%lld ", (ans+mod)%mod); return 0; }
D. Bash and a Tough Math Puzzle
题意： n 个数，两个操作：1、更改第 i 个数； 2、在区间 [l,r] 内，最多改变一个数，问是否能让 [l,r] 的gcd 等于 x 。
tags： 线段树单点更新，区间查询。如果区间内有超过 1 个数不是 x 的倍数，那就不能。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i<=b; ++i) #define per(i,b,a) for (int i=b; i>=a; --i) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second typedef long long ll; const int N = 500005; int n, tree[N<<2], cnt; void update(int ro, int L, int R, int x, int y) { if(L==R && L==x) { tree[ro] = y; return ; } int mid = L+R>>1; if(x <= mid) update(ro<<1, L, mid, x, y); else update(ro<<1|1, mid+1, R, x, y); tree[ro] = __gcd(tree[ro<<1], tree[ro<<1|1]); } bool query(int ro, int L, int R, int l, int r, int x) { if(cnt>1) return false; if(l<=L && R<=r) { if(tree[ro]%x==0) return true; if(L==R && tree[ro]%x!=0) { ++cnt; return false; } } int mid = L+R>>1; if(l<=mid) { query(ro<<1, L, mid, l, r, x); } if(mid<r) { query(ro<<1|1, mid+1, R, l, r, x); } if(cnt>1) return false; return true; } int main() { scanf("%d", &n); int ai, ti, l, r, x, y, q; rep(i,1,n) { scanf("%d", &ai); update(1, 1, n, i, ai); } scanf("%d", &q); while(q--) { scanf("%d", &ti); if(ti==1) { scanf("%d%d%d", &l, &r, &x); cnt = 0; if(query(1, 1, n, l, r, x)) puts("YES"); else puts("NO"); } else { scanf("%d%d", &x, &y); update(1, 1, n, x, y); } } return 0; }