A：暴力就行
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pii; typedef tuple<int,int,int> tu; const int N = 3e5 + 5; const int M = 1e3 + 5; const double eps = 1e-10; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e9 #define dbg(ax) cout << "now this num is " << ax << endl; inline int read() { int f = 1;int x = 0;char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } inline long long ADD(long long x,long long y) {return (x + y) % Mod;} inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;} inline long long MUL(long long x,long long y) {return x * y % Mod;} LL qucik_mi(LL a,LL b) { LL re = 1; while(b) { if(b & 1) re = re * a; a = a * a; b >>= 1; } return re; } void solve() { LL n; while(~scanf("%lld",&n)) { LL ans = 0; for(int i = 1;i <= 15;++i) { LL ma = qucik_mi(i,i); if(ma <= n) ans++; } printf("%lld ",ans); } } int main() { solve(); // system("pause"); return 0; }
B：这个题还是很不错的。
第一眼以为是二维的线段树，但是发现空间怎么都开不出来，而且要统计不同的颜色数。
观察这个矩阵可以发现，左边界都是在y轴上，那么我们要查询一个颜色在这里，就只需要找x最小的一个在1 ~ x1里。
那么对于y轴上我们就在y1 ~ y2里找。
那么方案就出来了，我们维护一棵y轴上的线段树，每个点维护最小的横坐标值。
因为只有50种，所以我们维护50课线段树就行。
但是如果真的维护50棵1 ~ 1e6的线段树，那空间肯定开不出来。
但是我们可以发现询问并不是很多，所以考虑动态开点维护线段树，一个点大概Logn的空间。
总空间m long n。
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pii; const int N = 2e5 + 5; const int M = 2e5 + 5; const double eps = 1e-10; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e9 #define dbg(ax) cout << "now this num is " << ax << endl; inline int read() { int f = 1;int x = 0;char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } inline long long ADD(long long x,long long y) {return (x + y) % Mod;} inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;} inline long long MUL(long long x,long long y) {return x * y % Mod;} int rt[55],top = 0,f = 0; struct {int L,r,mi;}node[N * 20]; void Pushup(int idx) { int l = node[idx].L,r = node[idx].r; if(l != 0) node[idx].mi = min(node[idx].mi,node[l].mi); if(r != 0) node[idx].mi = min(node[idx].mi,node[r].mi); } void build(int L,int r,int y,int x,int &idx) { if(idx == 0) { idx = ++top; node[idx].mi = x; } if(L == r) { node[idx].mi = min(node[idx].mi,x); return ; } int mid = (L + r) >> 1; if(mid >= y) build(L,mid,y,x,node[idx].L); else build(mid + 1,r,y,x,node[idx].r); Pushup(idx); } void query(int L,int r,int y1,int y2,int val,int idx) { if(idx == 0 || f) return ; if(L >= y1 && r <= y2) { if(node[idx].mi <= val) f = 1; return ; } int mid = (L + r) >> 1; if(mid >= y1) query(L,mid,y1,y2,val,node[idx].L); if(mid < y2) query(mid + 1,r,y1,y2,val,node[idx].r); } void solve() { while(1) { int op;op = read(); if(op == 3) break; if(op == 0) { for(int i = 0;i <= 50;++i) rt[i] = 0; for(int i = 1;i <= top;++i) node[i].L = node[i].r = 0,node[i].mi = INF; top = 0; } else if(op == 1) { int x,y,c;x = read(),y = read(),c = read(); build(1,1000000,y,x,rt[c]); } else { int x,y,c;x = read(),y = read(),c = read(); int ans = 0; for(int i = 0;i <= 50;++i) { f = 0; query(1,1000000,y,c,x,rt[i]); if(f) ans++; } printf("%d ",ans); } } } int main() { solve(); // system("pause"); return 0; }
C：三元环计数。(1：度不相同则，小度点向大度点连边，否则小编号向大编号连)
算出每条边在几个三元环里，然后求一下方案数即可。
需要注意的是，因为我们重构的是有向图，所以对于一个三元环，三条边都要加上1。
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pii; const int N = 1e5 + 5; const int M = 2e5 + 5; const double eps = 1e-10; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e9 #define dbg(ax) cout << "now this num is " << ax << endl; inline int read() { int f = 1;int x = 0;char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } inline long long ADD(long long x,long long y) {return (x + y) % Mod;} inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;} inline long long MUL(long long x,long long y) {return x * y % Mod;} int deg[N]; vector<pii> G[N]; pii px[M],py[M]; int vis[N],cnt[M],tag[N]; void solve() { int n,m; while(~scanf("%d %d",&n,&m)) { for(int i = 1;i <= n;++i) deg[i] = 0,G[i].clear(),vis[i] = tag[i] = 0; for(int i = 1;i <= m;++i) { cnt[i] = 0; deg[px[i].first = read()]++,deg[py[i].first = read()]++; px[i].second = py[i].second = i; } for(int i = 1;i <= m;++i) { if(deg[px[i].first] == deg[py[i].first]) { G[min(px[i].first,py[i].first)].push_back(pii{max(px[i].first,py[i].first),i}); } else if(deg[px[i].first] < deg[py[i].first]) G[px[i].first].push_back(pii{py[i].first,i}); else G[py[i].first].push_back(pii{px[i].first,i}); } for(int i = 1;i <= m;++i) { for(auto v : G[px[i].first]) { vis[v.first] = px[i].first; tag[v.first] = v.second; } for(auto v : G[py[i].first]) { if(vis[v.first] == px[i].first) { cnt[v.second]++; cnt[i]++; cnt[tag[v.first]]++; } } } LL ans = 0; for(int i = 1;i <= m;++i) ans += 1LL * cnt[i] * (cnt[i] - 1) / 2; printf("%lld ",ans); } } int main() { solve(); //system("pause"); return 0; }
D：这题很明显是找到递推式然后矩阵快速幂加速下。
但是在纸上推了很久的规律都没有找到。
这里看到了别人的一种很不错的做法：暴力dfs出前几项。
然后不断暴力枚举系数，从1个开始加。
当然这样如果递推式子涉及到后面很多项，复杂度容易超时。
优化：只枚举系数个数，然后高斯消元解方程就可以了。
当然上面这两种方案只满足都是线性递推的情况下。
不过矩阵快速幂一般都是线性的系数，所以很什么问题。
这里还有个问题，负数做乘法，会导致问题，因为存在负数的系数。
所以每次都要把负数转化成正数。
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pii; const int N = 1e5 + 5; const int M = 2e5 + 5; const double eps = 1e-10; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e9 #define dbg(ax) cout << "now this num is " << ax << endl; inline int read() { int f = 1;int x = 0;char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } inline long long ADD(long long x,long long y) {return (x + y) % Mod;} inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;} inline long long MUL(long long x,long long y) {return x * y % Mod;} bool vis[5][15]; void dfs(int x,int y,int sum,int n) { if(sum == 4 * n) { //ans++; return ; } if(vis[x][y]) { if(x == 4) dfs(1,y + 1,sum,n); else dfs(x + 1,y,sum,n); } else { if(x + 1 <= 4 && vis[x + 1][y] == 0) { vis[x + 1][y] = 1; vis[x][y] = 1; dfs(x + 1,y,sum + 2,n); vis[x + 1][y] = 0; vis[x][y] = 0; } if(y + 1 <= n && vis[x][y + 1] == 0) { vis[x][y + 1] = 1; vis[x][y] = 1; if(x == 4) dfs(1,y + 1,sum,n); else dfs(x + 1,y,sum + 2,n); vis[x][y + 1] = 0; vis[x][y] = 0; } } } /* 1 5 11 36 95 281 781 2245 6336 18061 dp[i] = dp[i - 1] + 5 * dp[i - 2] + dp[i - 3] - dp[i - 4] */ int dp[15]; void init() { //dfs(1,1,0,10); //dbg(ans); dp[1] = 1,dp[2] = 5,dp[3] = 11,dp[4] = 36,dp[5] = 95,dp[6] = 281,dp[7] = 781,dp[8] = 2245,dp[9] = 6336,dp[10] = 18061; for(int i = -10;i <= 10;++i) { for(int j = -10;j <= 10;++j) { for(int a = -10;a <= 10;++a) { for(int b = -10;b <= 10;++b) { int f = 0; for(int k = 5;k <= 10;++k) { if(dp[k] != i * dp[k - 1] + j * dp[k - 2] + a * dp[k - 3] + b * dp[k - 4]) f = 1; } if(f == 0) printf("%d %d %d %d ",i,j,a,b); } } } } } struct Mat{ LL m[5][5]; Mat operator * (const Mat a)const{ Mat c;memset(c.m,0,sizeof(c.m)); for(int i = 1;i <= 4;++i) { for(int j = 1;j <= 4;++j) { for(int k = 1;k <= 4;++k) { c.m[i][j] = ADD(c.m[i][j],MUL(m[i][k],a.m[k][j])); c.m[i][j] = ADD(c.m[i][j],Mod); } } } return c; } }; Mat quick_mi(Mat a,LL b) { Mat res;memset(res.m,0,sizeof(res.m)); for(int i = 1;i <= 4;++i) res.m[i][i] = 1; while(b) { if(b & 1) res = res * a; a = a * a; b >>= 1; } return res; } void solve() { LL n; while(~scanf("%lld",&n)) { Mat a;memset(a.m,0,sizeof(a.m)); a.m[1][1] = 1,a.m[1][2] = 5,a.m[1][3] = 1,a.m[1][4] = -1; a.m[2][1] = 1,a.m[3][2] = 1,a.m[4][3] = 1; Mat ans;memset(ans.m,0,sizeof(a.m)); ans.m[1][1] = 1,ans.m[2][1] = 5,ans.m[3][1] = 11,ans.m[4][1] = 36; a = quick_mi(a,n + 3); ans = a * ans; printf("%lld ",ans.m[1][1]); } } int main() { //init(); solve(); //system("pause"); return 0; }
E：统计一下二进制就行。
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pii; const int N = 1e5 + 5; const int M = 2e5 + 5; const double eps = 1e-10; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e9 #define dbg(ax) cout << "now this num is " << ax << endl; inline int read() { int f = 1;int x = 0;char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } inline long long ADD(long long x,long long y) {return (x + y) % Mod;} inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;} inline long long MUL(long long x,long long y) {return x * y % Mod;} int a[N],bit[30]; void solve() { int n,q; while(~scanf("%d %d",&n,&q)) { memset(bit,0,sizeof(bit)); int ans3 = 0; for(int i = 1;i <= n;++i) { a[i] = read(); ans3 ^= a[i]; for(int j = 0;j < 30;++j) { int g = (a[i] >> j) & 1; if(g == 1) bit[j]++; } } while(q--) { int p;p = read(); int ma3 = ans3 ^ a[p]; int ma1 = 0,ma2 = 0; for(int i = 0;i < 30;++i) { int g = (a[p] >> i) & 1; if(g == 0) { if(bit[i] == n - 1) ma1 += (1 << i); if(bit[i] > 0) ma2 += (1 << i); } else { if(bit[i] == n) ma1 += (1 << i); if(bit[i] > 1) ma2 += (1 << i); } } printf("%d %d %d ",ma1,ma2,ma3); } } } int main() { solve(); //system("pause"); return 0; }
F：这个题就是题意比较难读。
就是给你一个连通图，问你最小删多少的边的价值，使这个图无环。
我们可以考虑删完之后的图，我们要删的尽量小，那就是要让留下来的这个树（无环图，那就可以看成树）的总权值尽可能大。
那么就是求一棵最大生成树。
因为自己没写，贴一下队友的代码：
#include<bits/stdc++.h> using namespace std; #define ll long long #define Endl endl struct X{ int a,b,val; }r[200050]; int ef[100050]; int find(int g){return ef[g]==g?g:ef[g]=find(ef[g]);} bool cmp(X a,X b){return a.val>b.val;} int main() { ios::sync_with_stdio(false); int a,b,c,d,sum,s1,cnt; while(cin>>a>>b){ cnt=s1=sum=0; for(int i=1;i<=a;i++){ cin>>c>>c; ef[i]=i; } for(int i=0;i<b;i++){ cin>>r[i].a>>r[i].b>>r[i].val; s1+=r[i].val; } sort(r,r+b,cmp); for(int i=0;i<b;i++){ c=find(r[i].a); d=find(r[i].b); if(c!=d){ sum+=r[i].val; cnt++; ef[max(c,d)]=min(c,d); } } cout<<b-cnt<<' '<<s1-sum<<endl; } return 0; }
G：贪心一下就行。
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pii; const int N = 1e6 + 5; const int M = 2e5 + 5; const double eps = 1e-10; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e9 #define dbg(ax) cout << "now this num is " << ax << endl; inline int read() { int f = 1;int x = 0;char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } inline long long ADD(long long x,long long y) {return (x + y) % Mod;} inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;} inline long long MUL(long long x,long long y) {return x * y % Mod;} int a[N]; int cnt[N]; void solve() { int n; while(~scanf("%d",&n)) { memset(cnt,0,sizeof(cnt)); for(int i = 1;i <= n;++i) a[i] = read(),cnt[a[i]]++; sort(a + 1,a + n + 1); LL ans = 0; int len = unique(a + 1,a + n + 1) - a - 1; for(int i = 1;i <= len;++i) { while(cnt[a[i]] >= 3) { ans += 1; cnt[a[i]] -= 2; } if(cnt[a[i]] == 1) { if(a[i - 1] == a[i] - 1 && a[i] + 1 == a[i + 1] && cnt[a[i - 1]] > 0 && cnt[a[i + 1]] > 0) { ans++; cnt[a[i - 1]]--; cnt[a[i]]--; cnt[a[i] + 1]--; } } else if(cnt[a[i]] == 2){ if(i >= 2) { if(a[i - 2] == a[i - 1] - 1 && a[i - 1] == a[i] - 1 && a[i + 1] == a[i] + 1 && a[i + 2] == a[i + 1] + 1) { if(cnt[a[i - 2]] == 1 && cnt[a[i - 1]] == 1 && cnt[a[i + 1]] > 0 && cnt[a[i + 2]] > 0) { ans += 2; cnt[a[i - 2]]--; cnt[a[i - 1]]--; cnt[a[i]] -= 2; cnt[a[i + 1]]--; cnt[a[i + 2]]--; } else ans++,cnt[a[i]] -= 2; } else ans++,cnt[a[i]] -= 2; } else ans++,cnt[a[i]] -= 2; } } printf("%d ",ans); } } int main() { solve(); //system("pause"); return 0; }
J：这题也挺不错的。
一开始想的是树上合并01字典树。
但是空间开不出来。
然后就直接dsu on tree维护01字典树。
但是这里删点之后top++会可能导致超空间，re。
最后写了个队列回收之间的节点才过了。
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pii; const int N = 1e5 + 5; const int M = 2e5 + 5; const double eps = 1e-10; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e9 #define dbg(ax) cout << "now this num is " << ax << endl; inline int read() { int f = 1;int x = 0;char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } inline long long ADD(long long x,long long y) {return (x + y) % Mod;} inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;} inline long long MUL(long long x,long long y) {return x * y % Mod;} int val[N],son[N],sz[N],ans[N],top = 0,Son = 0; vector<int> G[N]; vector<pii> vec[N]; queue<int> Q; int tree[N * 50][2],cnt[N * 50][2]; void Insert(int ma) { int x = 0; for(int i = 29;i >= 0;--i) { int g = (ma >> i) & 1; if(tree[x][g] == 0) { if(top >= N * 49) { tree[x][g] = Q.front(); Q.pop(); } else { tree[x][g] = ++top; } cnt[x][g] = 1; } else cnt[x][g]++; x = tree[x][g]; } } void Delete(int ma) { int x = 0; for(int i = 29;i >= 0;--i) { int g = (ma >> i) & 1; if(tree[x][g] == 0) return ; int y = tree[x][g]; cnt[x][g]--; if(cnt[x][g] == 0) { Q.push(tree[x][g]); tree[x][g] = 0; } x = y; } } int query(int ma) { int x = 0; int ans = 0; for(int i = 29;i >= 0;--i) { int g = (ma >> i) & 1; if(tree[x][g ^ 1] == 0) { x = tree[x][g]; } else { ans += (1 << i); x = tree[x][g ^ 1]; } } return ans; } void dfs(int u) { sz[u] = 1; for(auto v : G[u]) { dfs(v); sz[u] += sz[v]; if(sz[v] > sz[son[u]]) son[u] = v; } } void solve(int u,int id) { if(id == 1) Insert(val[u]); else Delete(val[u]); for(auto v : G[u]) { if(v == Son) continue; solve(v,id); } } void dfs1(int u,int opt) { for(auto v : G[u]) { if(v == son[u]) continue; dfs1(v,0); } if(son[u]) dfs1(son[u],1),Son = son[u]; solve(u,1); Son = 0; for(auto v : vec[u]) { ans[v.first] = query(v.second); } if(opt == 0) solve(u,-1); } void solve() { int n,q; while(~scanf("%d %d",&n,&q)) { top = 0; while(!Q.empty()) Q.pop(); memset(cnt,0,sizeof(cnt)); memset(tree,0,sizeof(tree)); for(int i = 1;i <= n;++i) { val[i] = read(); G[i].clear(); vec[i].clear(); son[i] = 0; } for(int i = 1;i < n;++i) { int x;x = read(); G[x].push_back(i + 1); } dfs(1); for(int i = 1;i <= q;++i) { int u,x;u = read(),x = read(); vec[u].push_back(pii{i,x}); } dfs1(1,0); for(int i = 1;i <= q;++i) printf("%d ",ans[i]); } } int main() { solve(); //system("pause"); return 0; } /* 7 6 4 7 2 2 1 9 6 1 1 2 2 3 4 2 4 2 5 3 1 3 6 1 7 7 2 */