A - Coins
CodeForces - 1061A题意：需要几个硬币使得比S大
题解：除一下向上取整
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include<stack> #define INF 0x3f3f3f3f #define lowbit(x) (x&(-x)) using namespace std; typedef long long ll; const int maxn = 8e4 + 10; int main() { ll n,s; cin >> n >> s; ll tmp = ceil(s * 1.0 / (n * 1.0 )); printf("%lld ",tmp); }
B - Views Matter
CodeForces - 1061B
题意：n列，原来每列都放有a[ i ] 个盒子，问最多能移除多少个盒子后，使移除后的俯视图和右视图与移除前的相同
题解：每一列尽可能的只拿最上面的一个，接下来的剩下的在最高的一列拿，遍历一下就好了
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include<stack> #define INF 0x3f3f3f3f #define lowbit(x) (x&(-x)) using namespace std; typedef long long ll; const int maxn = 1e5 + 10; ll a[maxn]; int main() { ll n,m; scanf("%lld %lld",&n,&m); ll maxx = -1; ll sum = 0; for(int i=0;i<n;i++) { scanf("%lld",&a[i]); maxx = max(maxx,a[i]); sum += a[i]; } sort(a,a+n); int ans = 0; ll pos = 1; for(int i=0;i<n;i++) { if(a[i] >= pos) { ans++; pos++; } else { ans++; } } pos--; maxx = max(0LL,maxx - pos); // cout<<maxx<<endl; printf("%lld ",sum - (ans + maxx)); }
C - Multiplicity
CodeForces - 1061C
题意：给出序列ai，询问有多少个 a 的子序列 b 满足，对于任意的b[i]，b[i] mod i = 0
题解：先预处理因子，将每一个的倍数处理出来。之后开始dp累加前一个的方案数
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include<stack> #define INF 0x3f3f3f3f #define lowbit(x) (x&(-x)) using namespace std; typedef long long ll; const int maxn = 1e5 + 10; const int mod = 1e9 + 7; int n,a[maxn],dp[maxn * 10],ans; vector<int>fact[maxn * 10]; int maxx = -1; int main() { scanf("%d",&n); for(int i = 1; i <= n; i++) { scanf("%d",&a[i]); maxx = max(maxx,a[i]); } for(int i = 1; i <= maxx; i++) for(int j = 1; j <= maxx / i; j++) fact[i * j].push_back(i); for(int i = 1; i <= n; i++) sort(fact[a[i]].begin(),fact[a[i]].end()); dp[0] = 1; for(int i = 1; i <= n; i++) { for(int j = fact[a[i]].size() - 1; j >= 0; j--) { int x = fact[a[i]][j]; dp[x] += dp[x - 1]; dp[x] %= mod; //printf("i = %d dp[%d] = %d ",i,x,dp[x]); } } for(int i = 1; i <= n; i++) { ans += dp[i]; ans %= mod; } printf("%d ",ans); }
D - Sleepy Game
CodeForces - 937D题意：Petya and Vasya 在玩移动旗子的游戏， 谁不能移动就输了。 Vasya在订移动计划的时候睡着了， 然后Petya 就想趁着Vasya睡着的时候同时定下策略， 如果可以赢得话输出Win 并输出路径， 如果步数在达到1e6的情况下，就认定为平局， 输出Draw，如果输的话就输出lost。
题解：需要找到一条奇数路线的路径，dfs判环，一个奇数的环可以改变到达终点的奇偶步数
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include<stack> #define INF 0x3f3f3f3f #define lowbit(x) (x&(-x)) using namespace std; typedef long long ll; const int maxn = 1e5 + 10; vector<int>g[maxn]; vector<int>path; int vis[maxn][2]; int st[maxn]; int n,m; bool circle = false; void dfs(int x,int dep) { if(vis[x][dep & 1]) //vis的后面：1代表奇数步可达，0代表偶数不可达 return; vis[x][dep & 1] = 1; if(g[x].size() == 0 && (dep & 1)) { puts("Win"); for(int i = 0; i < path.size(); i++) printf("%d%c",path[i],i == path.size() - 1 ? ' ' : ' '); exit(0); } for(int i = 0; i < g[x].size(); i++) { int next = g[x][i]; if(st[next]) circle = true; path.push_back(next); st[next] = true; dfs(next,dep + 1); path.pop_back(); st[next] = false; } } int main() { scanf("%d %d",&n,&m); int tmp,u; for(int i = 1; i <= n; i++) { scanf("%d",&tmp); while(tmp--) { scanf("%d",&u); g[i].push_back(u); } } int start; scanf("%d",&start); st[start] = true; path.push_back(start); dfs(start,0); if(circle) puts("Draw"); else puts("Lose"); }
E - Tree Reconstruction
CodeForces - 1041E题意：构造题，一棵树删掉各条边后两部分的最大的顶点数告诉你了，问存不存在这么一棵树
题解：n肯定是会出现的，所以可以把n看作跟节点，如果一个顶点的最大次数只出现了1，那么他肯定是和根节点n直接相连的，如果出现了x次，那么这个点到根节点之间肯定有x-1个点，并且这x-1个点肯定比这个点的值要小，这就可以构造了
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<vector> #include<queue> #include<string.h> #include<cstring> using namespace std; #define LL long long const int MAXN = 1e3 + 10; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int cnt[MAXN]; struct Edge { int u,v; }edge[MAXN]; int vis[MAXN]; int main() { int n; while(cin >> n) { memset(vis,0,sizeof vis); memset(cnt,0,sizeof cnt); int x, y; for (int i = 0; i < n - 1; i++) { cin >> x >> y; cnt[x]++; cnt[y]++; } int tot = 0; int flag = 0; for (int i = n - 1; i >= 1; i--) { if (vis[i] == 0 && cnt[i] == 0) flag = 1; if (vis[i]) continue; int x = i, num = 0; if (cnt[x] == 1) { edge[++tot].u = x; edge[tot].v = n; continue; } for (int j = i - 1; j >= 1; j--) { if (cnt[j] == 0 && vis[j] == 0) { edge[++tot].u = x; edge[tot].v = j; x = j; vis[j] = 1; num++; } if (num == cnt[i] - 1) { edge[++tot].u = x; edge[tot].v = n; num++; break; } } if (num < cnt[i]) flag = 1; } if (flag) puts("NO"); else { puts("YES"); for (int i = 1; i <= tot; i++) printf("%d %d ", edge[i].u, edge[i].v); } } }