A - Infinite Sequence
CodeForces - 622A
题意：第一个数是1，接下来是1和2，接下来是1,2, 3，接下来是1,2,3, 4，问第n个数是什么
题解：找出第几轮在找出第几个
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #define INF 0x3f3f3f3f #define lowbit(x) (x&(-x)) using namespace std; typedef long long ll; const int maxn = 1e2 + 10; int main() { ll n; while(~scanf("%lld",&n)) { ll tmp; tmp = sqrt(2 * n * 1.0); if(tmp * (tmp + 1) > 2 * n) tmp--; if(n - (tmp * (tmp + 1)) / 2 == 0) printf("%lld ",tmp); else printf("%lld ",n - (tmp * (tmp + 1)) / 2); } }
B - Not Equal on a Segment
CodeForces - 622C
题意：给你一个数组，给你m个询问，每个询问一个区间， 一个数值，在区间里哪一个位置不是这个数值，输出任意一个就行
题解：找到区间里的不一样的两个数字比较一下就好了
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #define INF 0x3f3f3f3f #define lowbit(x) (x&(-x)) using namespace std; typedef long long ll; const int maxn = 2e5 + 10; int a[maxn]; struct node{ int st,en; int ans; }b[maxn]; int flag[maxn]; int main() { int n, q; scanf("%d %d", &n, &q); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); int pos = 0; for (int i = 1; i <= n; i++) { if(i == 1) { b[pos].st = i; b[pos].ans = a[i]; } else { if(a[i] != a[i-1]) { b[pos].en = i - 1; pos++; b[pos].st = i; b[pos].ans = a[i]; } } } b[pos].en = n; int id = 1; for(int i=0;i<=pos;i++) { for(int j=b[i].st;j<=b[i].en;j++) flag[j] = id; id++; } // for(int i=0;i<=pos;i++) // printf("%d %d %d ",b[i].st,b[i].en,b[i].ans); // cout<<endl; // for(int i=1;i<=n;i++) // printf("%d ",flag[i]); while(q--) { int l,r,x; scanf("%d %d %d",&l,&r,&x); if(flag[l] == flag[r] && a[l] == x) { puts("-1"); continue; } else if(flag[l] == flag[r] && a[r] != x) { printf("%d ",l); continue; } else { int id1 = flag[l]; id1--; if(b[id1].ans != x) printf("%d ",l); else { printf("%d ",b[id1 + 1].st); } } } }
C - Optimal Number Permutation
CodeForces - 622D
题意：用1-n组长度为2n的序列，要求每个数出现2次，假设位置分别为xi、yi(xi < yi)，定义di = yi-xi。让你找到一种排列使得sigma((n-i) * |di+i-n|)最小。
题解：贪心+找规律
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #define INF 0x3f3f3f3f #define lowbit(x) (x&(-x)) using namespace std; typedef long long ll; const int maxn = 2e6 + 10; int a[maxn]; int main() { int n; memset(a,0,sizeof a); scanf("%d",&n); int posa = 1; int posb = n + 1; for(int i=1;i<n;i++) { if(i % 2 == 1) { a[posa] = i; a[n + 1 - posa] = i; posa++; } else { a[posb] = i; a[3 * n - posb] = i; posb++; } } for(int i = 1;i <= 2 * n;i++) { if(a[i] == 0) printf("%d ",n); else printf("%d ",a[i]); } }
D - Ants in Leaves
CodeForces - 622E题意：给定一颗树，每个叶子节点上有一蚂蚁，除了根结点的之外的所有节点任意时刻至多只能有一个蚂蚁，每个蚂蚁每秒能移动到相邻的节点上，问所有蚂蚁移动到根结点的最短时间是多少。
题解：深度小的叶子蚂蚁先走，这样深度小的叶子蚂蚁就不用等深度大的叶子蚂蚁。然后算出每个子树走完的所需时间。d[i] = max(d[i - 1] + 1,d[i])
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #define INF 0x3f3f3f3f #define lowbit(x) (x&(-x)) using namespace std; typedef long long ll; const int maxn = 5e5 + 10; int n; vector<int>g[maxn],d; void dfs(int u,int fa,int deep) { if(g[u].size() == 1) { d.push_back(deep); // printf("%d ",deep); } for(int i=0;i<g[u].size();i++) { int v = g[u][i]; if(v == fa) continue; dfs(v,u,deep+1); } } int main() { while(~scanf("%d",&n)) { for(int i=1;i<=n;i++) g[i].clear(); for(int i=1;i<n;i++) { int u,v; scanf("%d %d",&u,&v); g[u].push_back(v); g[v].push_back(u); } int ans = 0; for(int k = 0; k < g[1].size(); k++) { d.clear(); dfs(g[1][k],1,1); sort(d.begin(),d.end()); for(int i = 1; i < d.size(); i++) { d[i] = max(d[i - 1] + 1,d[i]); //cout<<d[i]<<endl; } ans = max(ans,d.back()); } printf("%d ",ans); } return 0; }
E - The Sum of the k-th Powers
CodeForces - 622F
题意：求 
mod (1e9 + 7)
题解：朗格朗日差值板子
#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 = 1e6 + 10; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; LL n,k,ans,fac[MAXN],y[MAXN]; LL qpow(LL a, LL b) { LL s = 1; while(b) { if(b & 1) s = s * a % mod; a = a * a % mod; b >>= 1; } return s; } void init() { fac[0] = fac[1] = y[1] = 1; for(int i = 2; i < MAXN; i++) fac[i] = fac[i - 1] * i % mod; for(int i = 2; i < MAXN; i++) y[i] = (y[i - 1] + qpow(i,k)) % mod; } int main() { cin >> n >> k; init(); if(k == 0) cout << n << endl; else if(n <= k + 2) { cout << y[n] << endl; } else { LL sum = 1,sig; for(LL i = n - k - 2; i <= n - 1; i++) sum = sum * i % mod; for(LL i = 1; i <= k + 2; i++) { LL fz = sum * qpow(n - i,mod - 2) % mod; LL fm = qpow(fac[i - 1] * fac[k + 2 - i] % mod,mod - 2); if((k + 2 - i) % 2 == 0) sig = 1; else sig = -1; ans += sig * y[i] * fz % mod * fm % mod; ans %= mod; } cout << (ans % mod + mod) % mod << endl; } }