一场div3。。。
由于不计rating，所以打的比较浪，zhy直接开了个小号来掉分，于是他AK做出来了许多神仙题，但是在每一个程序里都是这么写的：
但是。。sbzhy每题交了两次，第一遍都是对的，结果就涨了。。
A - Uniform String
没什么意思。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cmath>
#include<cctype>
using namespace std;
typedef long long ll;
const int Maxn=610000;
int main() {
int t,n,k;
scanf("%d",&t);
while(t--) {
scanf("%d%d",&n,&k);
int x=n/k;
int y=n%k;
for(int i=0;i<k;i++)
if(y) {
for(int j=1;j<=x+1;j++) putchar(i+'a');
y--;
}
else for(int j=1;j<=x;j++) putchar(i+'a');
putchar('\n');
}
return 0;
}
B - Teams Forming
还是没什么意思。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cmath>
#include<cctype>
using namespace std;
typedef long long ll;
const int Maxn=610000;
int n,a[Maxn];
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1);
int ans=0;
for(int i=1;i<=n;i+=2) ans+=a[i+1]-a[i];
printf("%d",ans);
return 0;
}
C - Prefixes and Suffixes
这个大概就枚举长度为一的那个是前缀，然后挨着判断就好了。
不过我写的好麻烦啊。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cmath>
#include<cctype>
using namespace std;
typedef long long ll;
const int Maxn=210;
int n,p,s,ans[Maxn];
struct node{
char s[Maxn];
int len,bh;
}a[Maxn];
int cmp(node a,node b) {
return a.len<b.len;
}
bool pre(int x) {
for(int i=0;i<a[x].len-1;i++)
if(a[x].s[i]!=a[p].s[i]) return 0;
return 1;
}
bool suf(int x) {
for(int i=a[x].len-1;i>=0;i--)
if(a[x].s[i+1]!=a[s].s[i]) return 0;
return 1;
}
int main() {
scanf("%d",&n);int num=2*n-2;
for(int i=1;i<=num;i++) scanf("%s",a[i].s),a[i].len=strlen(a[i].s),a[i].bh=i;
sort(a+1,a+num+1,cmp);
int flag=0;ans[a[1].bh]=1;
p=1,s=2;
for(int i=3;i<=num;i+=2) {
if(!pre(i)&&!suf(i)) {
flag=1;
break;
}
else if(!pre(i)) {
if(!pre(i+1)) {
flag=1;
break;
}
ans[a[i+1].bh]=1;
p=i+1;
s=i;
}
else if(!suf(i)) {
if(!suf(i+1)) {
flag=1;
break;
}
ans[a[i].bh]=1;
p=i;
s=i+1;
}
else {
if(!suf(i+1)&&!pre(i+1)) {
flag=1;
break;
}
else if(!suf(i+1)) {
ans[a[i+1].bh]=1;
p=i+1;
s=i;
}
else {
ans[a[i].bh]=1;
p=i;
s=i+1;
}
}
}
if(!flag) {
for(int i=1;i<=num;i++)
if(ans[i]) putchar('P');
else putchar('S');
return 0;
}
memset(ans,0,sizeof(ans));
ans[a[2].bh]=1;p=2;s=1;
for(int i=3;i<=num;i+=2)
if(!pre(i)) {
ans[a[i+1].bh]=1;
p=i+1;
s=i;
}
else if(!suf(i)) {
ans[a[i].bh]=1;
p=i;
s=i+1;
}
else {
if(!suf(i+1)) {
ans[a[i+1].bh]=1;
p=i+1;
s=i;
}
else {
ans[a[i].bh]=1;
p=i;
s=i+1;
}
}
for(int i=1;i<=num;i++)
if(ans[i]) putchar('P');
else putchar('S');
return 0;
}
D1 - Great Vova Wall (Version 1)
考试的时候随便想了一个做法，然后没过。
正解就是先把所有数模2，维护一个栈表示有几段，然后每次加进来一个就可以把最后一个消掉或者再加上一个，如果最后还剩一个的话就可行，否则无解。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int Maxn=210000;
int n,x,s[Maxn],top;
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&x);
x%=2;
if(top==0||s[top]!=x) s[++top]=x;
else top--;
}
if(top<=1) puts("YES");
else puts("NO");
return 0;
}
D2 - Great Vova Wall (Version 2)
这个跟上一题不一样的地方在于不能竖着放，然后我随便想了一个交上，然而被hack了。
正解还是维护一个栈，但是这个栈是单调递减的，还是最后剩下一个就可行，注意正反都要处理一遍。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int Maxn=210000;
int s[Maxn],a[Maxn],n,top;
bool work() {
top=0;
for(int i=1;i<=n;i++)
if(top==0||a[i]!=s[top]) {
if(top&&a[i]>s[top]) {
puts("NO");
return 1;
}
s[++top]=a[i];
}
else top--;
if(top>1) {
puts("NO");
return 1;
}
return 0;
}
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
if(work()) return 0;
for(int l=1,r=n;l<r;l++,r--) swap(a[l],a[r]);
if(!work()) puts("YES");
return 0;
}
E - Minimal Diameter Forest
题意是给你一个森林，让你连成一颗树，让树的直径最小。
首先找到森林里每颗树的直径的中心，然后从里面找一个最深的，其他的都挂在上面就好啦。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int Maxn=2100;
int to[Maxn],nxt[Maxn],first[Maxn],tot=1;
int f[Maxn],g[Maxn],vis[Maxn],a[Maxn],num;
int n,m,u,v,zd,cd,rot,root,son[Maxn];
inline void add(int u,int v) {
to[tot]=v;
nxt[tot]=first[u];
first[u]=tot++;
to[tot]=u;
nxt[tot]=first[v];
first[v]=tot++;
}
void dfs(int root) {
vis[root]=1;
for(int i=first[root];i;i=nxt[i])
if(!vis[to[i]]) {
dfs(to[i]);int x=f[to[i]]+1;
if(x<=f[root]) g[root]=max(g[root],x);
else g[root]=f[root],f[root]=x,son[root]=to[i];
}
vis[root]=0;
}
void dfs2(int root) {
vis[root]=1;if(f[root]<f[::root]) ::root=root;
for(int i=first[root];i;i=nxt[i])
if(!vis[to[i]]) {
int x=f[root]+1;
if(son[root]==to[i]) x=g[root]+1;
if(x<=f[to[i]]) g[to[i]]=max(g[to[i]],x);
else g[to[i]]=f[to[i]],f[to[i]]=x,son[to[i]]=0;
dfs2(to[i]);
}
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) {
scanf("%d%d",&u,&v);
add(u,v);
}
f[0]=0x3f3f3f3f;rot=n+1;
for(int i=1;i<=n;i++)
if(!vis[i]) {
dfs(i);dfs2(i);
a[++num]=root;
if(f[root]>=f[rot]) rot=root;
root=0;
}
zd=f[rot],cd=g[rot];
for(int i=1;i<=num;i++) if(a[i]!=rot) {
if(f[a[i]]<zd) cd=max(cd,f[a[i]]+1);
else cd=zd,zd=f[a[i]]+1;
}
printf("%d\n",zd+cd);
for(int i=1;i<=num;i++) if(a[i]!=rot) printf("%d %d\n",rot,a[i]);
return 0;
}
F - Tree with Maximum Cost
这个题就是个裸换根DP，然后我还不会写。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cmath>
#include<cctype>
using namespace std;
typedef long long ll;
const int Maxn=410000;
int n,a[Maxn],to[Maxn],nxt[Maxn],first[Maxn],tot=1,fa[Maxn],u,v;
ll siz[Maxn],ans,f[Maxn];
inline void add(int u,int v) {
to[tot]=v;
nxt[tot]=first[u];
first[u]=tot++;
to[tot]=u;
nxt[tot]=u;
nxt[tot]=first[v];
first[v]=tot++;
}
void dfs(int root) {
siz[root]=a[root];
for(int i=first[root];i;i=nxt[i])
if(to[i]!=fa[root]) {
fa[to[i]]=root;
dfs(to[i]);
siz[root]+=siz[to[i]];
f[root]+=f[to[i]]+siz[to[i]];
}
}
void dfs2(int root) {
if(fa[root]) f[root]=f[fa[root]]+siz[1]-siz[root]*2;
for(int i=first[root];i;i=nxt[i])
if(to[i]!=fa[root]) dfs2(to[i]);
ans=max(ans,f[root]);
}
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<n;i++) {
scanf("%d%d",&u,&v);
add(u,v);
}
dfs(1);
dfs2(1);
printf("%I64d",ans);
return 0;
}
感觉自己菜的要死啊，照这么下去迟早要变成pupil啊。。