BunnyOJ Test Round

布满荆棘的人生 2021-10-26 11:29 132阅读 0赞

\\(BunnyOJ\\)的测试赛。由\\(@\{T\}\\color\{red\}\{sukimaru\}\\)和\\(@\{l\}\\color\{red\}\{igen\}\\)举办。

\\(B\\)：\\(sum\\) \\(from\\) \\(LibreOJ\\)

给你\\(n\\)个数，请你在其中找出一些数，使得它们的和能被\\(n\\)整除。输出任意一组解（下标&值）即可。

数据范围：\\(1 \\leq n \\leq 1000010\\)，\\(0 \\leq a\_i \\leq 10^\{10\}\\)

将序列前缀和一下。将前缀和后的\\(c\[\]\\)数组\\(mod\\) \\(n\\)，此时如果有\\(c\_i = 0\\)，那么\\(a\_1...a\_i\\)就是一个\\(ans\\)。

如果不存在\\(c\_i = 0\\)，由于\\(k mod n\\)只有\\(0...n-1\\)共\\(n\\)种取值，那么\\(c\[\]\\)中\\(n\\)个数，必定存在一组\\(c\[i\] = c\[j\]\\)且\\(i \\leq j\\)。此时\\(a\_\{i+1\}...aj\\)就是一个\\(ans\\).

算法复杂度：\\(O(n)\\)

#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> using namespace std; long long c[1000233],a[1000233]; int book[1000233]={}; int main() { int n; scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%lld",&c[i]); a[i]=c[i]; c[i]%=n; c[i]+=c[i-1]; // printf("%lld ",c[i]); } // printf("\n"); for (int i=1;i<=n;i++) { if (!(c[i]%n)) { for (int j=1;j<=i;j++) { printf("%d %lld\n",j,a[j]); } return 0; } } for (int i=1;i<=n;i++) { if (!book[c[i]%n]) { book[c[i]%n]=i; continue; } for (int j=book[c[i]%n]+1;j<=i;j++) { printf("%d %lld\n",j,a[j]); } return 0; } }

\\(C\\)：最小字典序 \\(from\\) \\(51nod\\)

给出一个字符串S，你需要从S中挑选一对字符进行一次交换（不可以不交换），并让得到的新字符串字典序最小。输出这个字典序最小的字符串。

数据范围：\\(2 \\leq |S| \\leq 500000\\)，\\(S\\)只包含\\(a...z\\)的小写字母。

考场上yy了一个假的单调栈做法，\\(Bunnycxk\\)一看觉得不对劲这sb做法怎么\\(AC\\)了，然后当场改数据把我卡到20。

其实正解很sb。

维护每个字母在原串中出现的次数以及在原串中最后一次出现的位置。

如果原串是不递减的，那么如果原串有两个相同字符，交换这两个字符。否则将最后两个字符交换。

否则，枚举原串的每一位\\(s\_i\\)，如果存在尽量小的小于\\(s\_i\\)的字符\\(s\_j\\)且\\(i \\leq j\\)，交换\\(s\_i\\)，\\(s\_j\\)。

算法复杂度：\\(O(n)\\)

#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> #define MAXN 500233 using namespace std; string s; int tag[MAXN],sum[MAXN]={}; int main() { cin>>s; int len=s.size(); bool flag=0; for (int i=0;i<len;i++) { tag[s[i]-'a']=i; sum[s[i]-'a']++; if (s[i]<s[i-1]) flag=1; } if (!flag) { for (int i=0;i<len;i++) { if (sum[s[i]-'a']>1) { cout<<s; return 0; } } swap(s[len-1],s[len-2]); cout<<s; return 0; } for (int i=0;i<len;i++) { for (int j=0;j<s[i]-'a';j++) { if (tag[j]>i) { // printf(":::%d %d\n",s[i],j); swap(s[i],s[tag[j]]); // printf("qwq"); cout<<s; return 0; } } } }

\\(D\\)：\\(262144\\) \\(from\\) \\(USACO\\)

给你一个长度为\\(n\\)的正整数数列，每个数在 \\(1\\)到\\(40\\)之间。  
你可以对序列进行操作，每次操作，你可以把两个相邻且相同的数替换成比他们值大\\(1\\)的数，例如两个相邻的\\(7\\)替换成\\(8\\)。当无法再合并时，游戏结束。游戏目标是使游戏结束时数列中的最大值尽可能大。输出这个最大值。

数据范围：\\(n \\leq 262144\\)

区间\\(DP\\)..应该叫这个名字。

用\\(f\[i\]\[j\]\\)表示以\\(j\\)为左界，合并后值为\\(i\\)的右界。

那么我们求\\(f\[i\]\[j\]\\)，需要两个合并后值为\\(i-1\\)的相邻的区间。那左边那个区间的左界就是\\(j\\)。

很容易得到左边那个区间是\\(j...f\[i-1\]\[j\]\\)，右边区间的左界就是\\(f\[i-1\]\[j\]+1\\)（左边区间的右界+1）。

由此可得

\\\[f\[i\]\[j\]=f\[i-1\]\[f\[i-1\]\[j\]+1\]\\\]

同时要考虑边界问题以及存在性问题。如果本身没有合法的\\(f\[i-1\]\[j\]\\)，那么就不能更新\\(f\[i\]\[j\]\\)。如果\\(f\[i-1\]\[j\]+1>n\\)，也无法合并区间。

对于\\(f\[i\]\[j\]!=0\\)的\\(max\{i\}\\)即为\\(ans\\)。

算法复杂度：\\(O(n)\\)

#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> #define MAXN 262233 using namespace std; int n; int f[80][MAXN],a[MAXN]; int main() { scanf("%d",&n); int maxn=-1; for (int i=1;i<=n;i++) { scanf("%d",&a[i]); f[a[i]][i]=i; maxn=max(maxn,a[i]); } maxn+=37; int ans=-1; for (int i=2;i<=maxn;i++) { for (int j=1;j<=n;j++) { if (f[i-1][j]<n&&f[i-1][j]>0) { f[i][j]=f[i-1][f[i-1][j]+1]; } if (f[i][j]!=0) ans=max(ans,i); } } printf("%d",ans); return 0; }

\\(F\\)：\\(colorful\\) \\(tree\\) \\(by\\) \\(ATcoder\\) \\(Beginner\\) \\(Contest\\)

有一棵\\(n\\)个节点的树，每个节点编号为\\(1\\)到\\(n\\) 。树上的第\\(i\\)条边连接点\\(a\_i\\)和\\(b\_i\\)颜色为\\(c\_i\\)，长度为\\(d\_i\\) 。在这里， \\(c\_i\\)是\\(1\\)到\\(n-1\\)之间的整数。

给出\\(Q\\)个询问，第\\(j\\)个询问给出 ，表示询问：如果将颜色为\\(x\_j\\)的边长度全部改为\\(y\_j\\) ，请你计算点\\(u\_j\\)到点\\(v\_j\\)的路径长度。

所有询问互不影响。

数据范围：\\(2 \\leq n,q \\leq 10^5\\)，\\(1 \\leq x\_i,y\_i,u\_j,v\_j \\leq n\\)，\\(1 \\leq c\_i,x\_j \\leq n\\)，\\(1 \\leq d\_i,y\_j \\leq 10^4\\)

我们可以树剖处理+动态开点线段树维护。这样是两个\\(log\\)的。

询问互不影响，考虑离线处理。将每个询问处理为三个部分：

点\\(u,v\\)的\\(ans\\)，相当于\\(ans(1,u)+ans(1,v)-2\*ans(1,lca(u,v))\\)。所以对于每个询问拆成的三个询问都是点到根。

那么我们可以在处理一个节点的时候就处理与这个节点相关的询问的这个节点的部分。标记子询问所属询问的编号，将\\((1,u)\\)，\\((1,v)\\)询问的贡献倍数设为\\(1\\)，\\((1,lca(u,v))\\)的贡献倍数设为\\(-2\\)。

#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <vector> #define MAXN 100233 using namespace std; int dep[MAXN],fa[MAXN],siz[MAXN],son[MAXN],top[MAXN]; struct pvp { int c,w,id,add; }; vector<pvp> a[MAXN]; struct qwq { int nex,to,w,c; }e[MAXN<<1]; int h[MAXN]; int tot=0; int sum[MAXN]; int ans[MAXN]; inline void add(int x,int y,int w,int c) { e[++tot].to=y; e[tot].nex=h[x]; e[tot].w=w; e[tot].c=c; h[x]=tot; } void dfs_fir(int f,int x,int dept) { dep[x]=dept; fa[x]=f; siz[x]=1; int maxn=-1; for (int i=h[x],y;i;i=e[i].nex) { y=e[i].to; if (y==f) continue; sum[y]=sum[x]+e[i].w; dfs_fir(x,y,dept+1); siz[x]+=siz[y]; if (siz[y]>maxn) { son[x]=y; maxn=siz[y]; } } } void dfs_sec(int x,int tp) { top[x]=tp; if (!son[x]) return; dfs_sec(son[x],tp); for (int i=h[x],y;i;i=e[i].nex) { y=e[i].to; if (y==fa[x]||y==son[x]) continue; dfs_sec(y,y); } } inline int LCA(int x,int y) { while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); x=fa[top[x]]; } if (dep[x]>dep[y]) return y; return x; } int icnt[MAXN],wcnt[MAXN]; void dfs(int x) { for (int i=h[x],y;i;i=e[i].nex) { y=e[i].to; if (y==fa[x]) { continue; } icnt[e[i].c]++; wcnt[e[i].c]+=e[i].w; dfs(y); icnt[e[i].c]--; wcnt[e[i].c]-=e[i].w; } for (int i=0;i<a[x].size();i++) { ans[a[x][i].id]+=(sum[x]*a[x][i].add); ans[a[x][i].id]-=(wcnt[a[x][i].c]-icnt[a[x][i].c]*a[x][i].w)*a[x][i].add; } } int main() { int n,m; scanf("%d%d",&n,&m); int u,v,w,c; for (int i=1;i<n;i++) { scanf("%d%d%d%d",&u,&v,&c,&w); add(u,v,w,c); add(v,u,w,c); } dfs_fir(1,1,1); dfs_sec(1,1); for (int i=1;i<=m;i++) { scanf("%d%d%d%d",&c,&w,&u,&v); a[u].push_back((pvp){c,w,i,1}); a[v].push_back((pvp){c,w,i,1}); a[LCA(u,v)].push_back((pvp){c,w,i,-2}); } dfs(1); for (int i=1;i<=m;i++) { printf("%d\n",ans[i]); } return 0; }

转载于:https://www.cnblogs.com/Kan-kiz/p/11320573.html