A. Hard to prepare
#include <bits/stdc++.h> using namespace std; const int MOD = 1e9+7; long long bit[1000010]; long long f[1000010]; int main() { int T; int n,k; bit[0] = 1; for (int i = 1; i <= 1000000; i++) { bit[i] = 2*bit[i-1]%MOD; } scanf("%d", &T); while (T--) { scanf("%d%d", &n, &k); f[1] = bit[k]; long long t1 = (bit[k]-1+MOD)%MOD; long long t2 = (bit[k]-2+MOD)%MOD; f[2] = f[1]*t1%MOD; for (int i = 3; i <= n; i++) { f[i] = (f[i-2]*t1%MOD+(f[i-1]-f[1])*t2%MOD)%MOD; f[i] = (f[i] + MOD)%MOD; } printf("%d ", (int)f[n]); } return 0; }
B. BE, GE or NE
#include <bits/stdc++.h> using namespace std; int n; int dp[1010][210]; int a[1010][3]; const int INF = 0x3f3f3f3f; int gao(int i, int now) { if (i >= n) return now-100; if (dp[i][now] != INF) { return dp[i][now]; } if (i%2 == 0) { int ans = -100; int tmp = now-100; if (a[i][0] > 0) { int nn = min(tmp+a[i][0], 100); ans = max(ans, gao(i+1, nn+100)); } if (a[i][1] > 0) { int nn = max(tmp-a[i][1], -100); ans = max(ans, gao(i+1, nn+100)); } if (a[i][2] > 0) { ans = max(ans, gao(i+1, -tmp+100)); } dp[i][now] = ans; return ans; } else { int ans = 100; int tmp = now-100; if (a[i][0] > 0) { int nn = min(tmp+a[i][0], 100); ans = min(ans, gao(i+1, nn+100)); } if (a[i][1] > 0) { int nn = max(tmp-a[i][1], -100); ans = min(ans, gao(i+1, nn+100)); } if (a[i][2] > 0) { ans = min(ans, gao(i+1, -tmp+100)); } dp[i][now] = ans; return ans; } } int main() { int m,k,l; while(scanf("%d%d%d%d", &n, &m, &k, &l) == 4) { for (int i = 0; i < n; i++) { scanf("%d%d%d", &a[i][0], &a[i][1], &a[i][2]); } for (int i = 0; i <= n; i++) for (int j = 0; j <= 200; j++) dp[i][j] = INF; int ans = gao(0, m+100); if (ans >= k)puts("Good Ending"); else if(ans <= l) puts("Bad Ending"); else puts("Normal Ending"); } return 0; }
C. Cacti Lottery
#include <bits/stdc++.h> using namespace std; int getScore(int s) { switch(s) { case 6: return 10000; case 7: return 36; case 8: return 720; case 9: return 360; case 10: return 80; case 11: return 252; case 12: return 108; case 13: return 72; case 14: return 54; case 15: return 180; case 16: return 72; case 17: return 180; case 18: return 119; case 19: return 36; case 20: return 360; case 21: return 1080; case 22: return 144; case 23: return 1800; case 24: return 3600; } } char mp[10][10]; int a[3][3]; double sum; double num; long long cnt = 0; double r[3]; double c[3]; double dd[2]; void gao(bool used[], int x, int y) { /* if (x >= 3) { printf("*** x %d y %d ",x, y); for (int i = 1; i <= 9; i++) printf("%d ", used[i]); printf(" "); for(int i = 0; i < 3; i++) { for(int j = 0;j < 3; j++) printf("%d ", a[i][j]); printf(" "); } } */ if (x >= 3) { for (int i = 0; i < 3; i++) { int tmp = 0; for (int j = 0; j < 3; j++) tmp += a[i][j]; r[i] += getScore(tmp); } for (int j = 0; j < 3; j++) { int tmp = 0; for (int i = 0; i < 3; i++) { tmp += a[i][j]; } c[j] += getScore(tmp); } dd[0] += getScore(a[0][0] + a[1][1] + a[2][2]); dd[1] += getScore(a[2][0] + a[1][1] + a[0][2]); cnt++; return; } int nx = x; int ny = y+1; if (ny >= 3) { ny = 0; nx++; } if (mp[x][y] != '#') { gao(used, nx, ny); } else { for (int i = 1; i <= 9; i++) { if (!used[i]) { used[i] = true; a[x][y] = i; gao(used, nx, ny); a[x][y] = 0; used[i] = false; } } } } void dfs(bool used[], int x, int y) { /* if (x >= 3) { printf("x %d y %d ",x, y); for (int i = 1; i <= 9; i++) printf("%d ", used[i]); printf(" "); for(int i = 0; i < 3; i++) { for(int j = 0;j < 3; j++) printf("%d ", a[i][j]); printf(" "); } } */ if (x >= 3) { cnt = 0; for (int i = 0; i < 3; i++) { r[i] = 0; c[i] = 0; } dd[0] = 0; dd[1] = 0; gao(used, 0, 0); double tmp = 0; for (int i = 0; i < 3; i++) { tmp = max(tmp, r[i]); tmp = max(tmp, c[i]); } tmp = max(tmp, dd[0]); tmp = max(tmp, dd[1]); sum += tmp/cnt; num += 1; return; } int nx = x; int ny = y+1; if (ny >= 3) { nx++; ny = 0; } if (mp[x][y] != '*') { dfs(used, nx, ny); } else { for (int i = 1; i <= 9; i++) { if (!used[i]) { used[i] = true; a[x][y] = i; dfs(used, nx, ny); a[x][y] = 0; used[i] = false; } } } } int main() { int T; scanf("%d", &T); while (T--) { for (int i = 0; i < 3; i++) scanf("%s", mp[i]); sum = 0; num = 0; bool used[10]; memset(used, false, sizeof(used)); memset(a, 0, sizeof(a)); for(int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) { if (mp[i][j] >= '1' && mp[i][j] <= '9') { used[mp[i][j] -'0'] = true; a[i][j] = mp[i][j]-'0'; } } dfs(used, 0, 0); printf("%.10f ", sum/num); } return 0; }
D. Easy Math
E. End Fantasy VIX
F. Features Track
#include<iostream> #include<string> #include<map> #include<vector> #include<set>; using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; const int maxn = 1e6 + 1; int t; int n, m; pair<int,int>s; map<pair<int, int>, int>sum; map<pair<int, int>, int>flag; set<pair<int,int> >v; int main() { scanf("%d", &t); while(t--) { int ans = 0; v.clear(); sum.clear(); scanf("%d", &n); while(n--) { flag.clear(); scanf("%d", &m); if(m == 0) { v.clear(); sum.clear(); } for(int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); s.first = a; s.second = b; if(!flag[s]) sum[s]++; flag[s] = 1; v.insert(s); ans = max(ans, sum[s]); } pair<int, int> cnt[110000]; int d = 0; for(set<pair<int,int> >::iterator it = v.begin();it != v.end();it++) { if(flag[*it] == 0) cnt[d++] = *it; } for(int i = 0; i < d; i++) { v.erase(cnt[i]); sum[cnt[i]] = 0; } } printf("%d ",ans); } return 0; }
G. Trace
#include <bits/stdc++.h> using namespace std; long long gao(vector<int> vec) { int sz = vec.size(); set<int>st; long long ans = 0; for (int i = sz-1; i >= 0; i--) { set<int>::iterator it = st.lower_bound(vec[i]); if (it == st.begin()) { ans += vec[i]; } else { it--; ans += vec[i] - *it; } st.insert(vec[i]); } return ans; } int main() { int n; while(scanf("%d", &n) == 1) { vector<int>vec1, vec2; int x,y; while(n--) { scanf("%d%d", &x, &y); vec1.push_back(x); vec2.push_back(y); } cout<<gao(vec1) + gao(vec2)<<endl; } }
H. Ryuji doesn't want to study
#include <iostream> #include <stdio.h> #define ll long long #define lson l, mid, rt << 1 #define rson mid + 1, r, rt << 1 | 1 using namespace std; int n; const int MAXN = 1e5 + 10; ll sum[MAXN << 2]; ll add[MAXN << 2]; void push_up(int rt){//向上更新 sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; } void push_down(int rt, int m){ if(add[rt]){//若有标记,则将标记向下移动一层 add[rt << 1] += add[rt]; add[rt << 1 | 1] += add[rt]; sum[rt << 1] += (m - (m >> 1)) * add[rt]; sum[rt << 1 | 1] += (m >> 1) * add[rt]; add[rt] = 0;//取消本层标记 } } void build(int l, int r, int rt){//建树 add[rt] = 0; if(l == r){ scanf("%lld", &sum[rt]); return; } int mid = (l + r) >> 1; build(lson); build(rson); push_up(rt);//向上更新 } void update(int L, int R, ll key, int l, int r, int rt){//区间更新 if(L <= l && R >= r){ sum[rt] = (r - l + 1) * key; add[rt] = key; return; } push_down(rt, r - l + 1);//向下更新 int mid = (l + r) >> 1; if(L <= mid) update(L, R, key, lson); if(R > mid) update(L, R, key, rson); push_up(rt);//向上更新 } ll query(int L, int R, int l, int r, int rt){//区间求和 if(L <= l && R >= r) return sum[rt]; push_down(rt, r - l + 1);//向下更新 int mid = (l + r) >> 1; ll ans = 0; if(L <= mid) ans += query(L, R, lson); if(R > mid) ans += query(L, R, rson); return ans; } //----------------------------------- ll sum2[MAXN << 2]; ll add2[MAXN << 2]; void push_up2(int rt){//向上更新 sum2[rt] = sum2[rt << 1] + sum2[rt << 1 | 1]; } void push_down2(int rt, int m){ if(add2[rt]){//若有标记,则将标记向下移动一层 add2[rt << 1] += add2[rt]; add2[rt << 1 | 1] += add2[rt]; sum2[rt << 1] += (m - (m >> 1)) * add2[rt]; sum2[rt << 1 | 1] += (m >> 1) * add2[rt]; add2[rt] = 0;//取消本层标记 } } void build2(int l, int r, int rt){//建树 add2[rt] = 0; if(l == r){ sum2[rt]=sum[rt]*(n-l+1); return; } int mid = (l + r) >> 1; build2(lson); build2(rson); push_up2(rt);//向上更新 } void update2(int L, int R, ll key, int l, int r, int rt){//区间更新 if(L <= l && R >= r){ sum2[rt] = (r - l + 1) * key; add2[rt] = key; return; } push_down2(rt, r - l + 1);//向下更新 int mid = (l + r) >> 1; if(L <= mid) update2(L, R, key, lson); if(R > mid) update2(L, R, key, rson); push_up2(rt);//向上更新 } ll query2(int L, int R, int l, int r, int rt){//区间求和 if(L <= l && R >= r) return sum2[rt]; push_down2(rt, r - l + 1);//向下更新 int mid = (l + r) >> 1; ll ans = 0; if(L <= mid) ans += query2(L, R, lson); if(R > mid) ans += query2(L, R, rson); return ans; } int main(void){ int m; scanf("%d%d", &n, &m); build(1, n, 1); build2(1, n, 1); while(m--){ ll x, y; ll z; scanf("%lld%lld%lld",&x,&y,&z); if(x==1){ ll ans=query(y,z,1,n,1); ll ans2=query2(y,z,1,n,1); printf("%lld ",ans2-ans*(n-z)); }else{ update(y,y,z,1,n,1); update2(y,y,z*(n-y+1),1,n,1); } } }
I. Characters with Hash
#include<iostream> #include<string> using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; const int maxn = 1e6 + 1; int t; int n; char ch[2]; string str; int main() { scanf("%d", &t); while(t--) { int num; ll ans = 0; int cnt = 0; scanf("%d %s", &n, ch); cin>>str; int len = str.size(); int flag=0; for(int i = 0;i < len; i++) { num = abs(str[i]- ch[0]); if(flag==0) { if (num != 0) { if (num / 10 == 0) { ans += 1; } else if (num / 100 == 0) { ans += 2; } flag = 1; } }else{ ans+=2; } } if(ans == 0) ans++; printf("%lld ",ans); } return 0; }
J. Maze Designer
#include <bits/stdc++.h> using namespace std; const int MAXN = 250010; const int DEG = 20; struct Edge{ int to,next; int w; }edge[MAXN*2]; int head[MAXN],tot; void addedge(int u,int v, int w){ edge[tot].to = v; edge[tot].next = head[u]; edge[tot].w = w; head[u] = tot++; } void init(){ tot = 0; memset(head,-1,sizeof(head)); } int fa[MAXN][DEG];//`fa[i][j]琛ㄧず缁撶偣i鐨勭�`2^j`涓��鍏坄 int deg[MAXN];//`娣卞害鏁扮粍` void BFS(int root){ queue<int>que; deg[root] = 0; fa[root][0] = root; que.push(root); while(!que.empty()){ int tmp = que.front(); que.pop(); for(int i = 1;i < DEG;i++) fa[tmp][i] = fa[fa[tmp][i-1]][i-1]; for(int i = head[tmp]; i != -1;i = edge[i].next){ int v = edge[i].to; if(v == fa[tmp][0])continue; deg[v] = deg[tmp] + 1; fa[v][0] = tmp; que.push(v); } } } int LCA(int u,int v){ if(deg[u] > deg[v])swap(u,v); int hu = deg[u], hv = deg[v]; int tu = u, tv = v; for(int det = hv-hu, i = 0; det ;det>>=1, i++) if(det&1) tv = fa[tv][i]; if(tu == tv)return tu; for(int i = DEG-1; i >= 0; i--){ if(fa[tu][i] == fa[tv][i]) continue; tu = fa[tu][i]; tv = fa[tv][i]; } return fa[tu][0]; } struct Node { int u,v,w; }node[501000]; bool cmp(Node a, Node b) { return a.w > b.w; } int F[501000]; int find(int x) { if(F[x] == -1)return x; else return F[x] = find(F[x]); } void bing(int x, int y) { int t1 = find(x); int t2 = find(y); if (t1 != t2)F[t1] = t2; } int main() { int n,m; while(scanf("%d%d", &n, &m) == 2) { int cnt = 0; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { int u = i*m + j; char op[4]; int w; for(int t = 0; t<2; t++) { scanf("%s%d", op, &w); if (op[0] == 'X')continue; int v; if (op[0] == 'D' && i < n-1) { v = (i+1)*m + j; } else if (op[0] == 'R' && j < m-1) { v = i*m+j+1; } else { continue; } node[cnt].u = u; node[cnt].v = v; node[cnt++].w = w; } } sort(node, node+cnt, cmp); init(); memset(F, -1, sizeof(F)); for (int i = 0; i < cnt; i++) { int u = node[i].u; int v = node[i].v; if (find(u) != find(v)) { bing(u, v); addedge(u,v,node[i].w); addedge(v,u,node[i].w); } } BFS(0); int Q; scanf("%d", &Q); int x1,y1,x2,y2; while(Q--) { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); int u = (x1-1)*m+y1-1; int v = (x2-1)*m + y2-1; int lca = LCA(u,v); printf("%d ", deg[u]+deg[v] - 2*deg[lca]); } return 0; } return 0; }
K. Morgana Net