A - Repeating Cipher
我做的好慢啊。
#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;
char s[Maxn],a[Maxn];
int main() {
scanf("%d",&n);
scanf("%s",s);
int temp=0;
while(temp*(temp+1)/2<n) temp++;
for(int i=temp;i>=1;i--)
a[i-1]=s[i*(i+1)/2-1];
printf("%s
",a);
return 0;
}
B - Array Stabilization
删掉的肯定是最大或最小，那么记下来最大，次大，最小，次小，然后就可以输出了。
#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,x;
int main() {
scanf("%d",&n);
int zd=0,cd=0,zx=0x7fffffff,cx=zx;
while(n--) {
scanf("%d",&x);
if(x>zd) {
cd=zd;zd=x;
}
else cd=max(cd,x);
if(x<zx) {
cx=zx;zx=x;
}
else cx=min(cx,x);
}
printf("%d
",min(cd-zx,zd-cx));
return 0;
}
C - Powers Of Two
首先把n分解一下，如果k比n大，显然无解，如果k个数组成不了n，显然无解，然后每次把一个二的幂拆成两个，如果拆成了1就特判一下，然后输出即可。
#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,k,a[Maxn],tot,cnt;
int main() {
scanf("%d%d",&n,&k);
if(n<k) {
puts("NO");
return 0;
}
int temp=1;
while(n) {
if(n&1) a[++tot]=temp;
temp<<=1,n>>=1;
}
if(tot>k) {
puts("NO");
return 0;
}
k-=tot;
while(k) {
int temp=a[tot];
tot--;
if(temp==1)
cnt++;
else {
temp>>=1;
a[++tot]=temp;
a[++tot]=temp;
k--;
}
}
puts("YES");
for(int i=1;i<=cnt;i++) printf("1 ");
for(int i=1;i<=tot;i++) printf("%d ",a[i]);
return 0;
}
D - Circular Dance
首先如果n==3，那么就随便输出，否则的话，因为每个人都记下来了下面的两个人，所以就能判断出来哪个和他紧挨着，然后就能求出来了。
#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,x[Maxn],y[Maxn],nxt[Maxn];
int main() {
scanf("%d",&n);
if(n==3) {
puts("1 2 3");
return 0;
}
for(int i=1;i<=n;i++)
scanf("%d%d",&x[i],&y[i]);
int temp=1,tempp;
if(x[x[1]]==y[1]||y[x[1]]==y[1]) tempp=x[1];
else tempp=y[1];
nxt[temp]=tempp;
while(tempp!=1) {
int sxz;
if(x[temp]==tempp) sxz=y[temp];
else sxz=x[temp];
temp=tempp;tempp=sxz;
nxt[temp]=tempp;
}
int now=nxt[1];printf("1 ");
while(now!=1) {
printf("%d ",now);
now=nxt[now];
}
return 0;
}
E - Almost Regular Bracket Sequence
首先肯定是把左括号换成1，右括号换成-1，求一下和。因为变了一个括号，那么总和变化值一定是2或-2，那么如果总和不是2或-2，一定无解。
如果总和是-2，那么一定是一个右括号变成了左括号，那么我们就把所有的右括号变成左括号，左括号变成右括号，然后把序列倒过来，就可以变成总和为2的情况。
然后我们考虑一下总和为2的情况怎么做。首先还是从左到右扫，考虑一下如果把一个左括号变成右括号，那么会使得现在的总和-2。所以我们记下来前缀总和和前缀左括号数，如果前缀总和小于0，那么就无解，然后因为在这个位置左边把一个左括号变成右括号，势必会使这个位置的和-2，那么如果这个位置的和小于2，在这个位置左边都没有解，就把前缀左括号数清零即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cctype>
using namespace std;
char gc() {
// static char buf[100000],*p1,*p2;
// return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
return getchar();
}
template<class T>
int read(T& ans) {
ans=0;T f=1;
char ch=gc();
while(!isdigit(ch)) { if(ch=='-') f=-1; if(ch==EOF) return -1; ch=gc(); }
while(isdigit(ch)) ans=ans*10+ch-'0',ch=gc();
ans*=f;
return 1;
}
typedef long long ll;
const int Maxn=2100000;
const int inf=0x3f3f3f3f;
int n,a[Maxn],sum,ans;
char s[Maxn];
int main() {
// freopen("test.in","r",stdin);
scanf("%d%s",&n,s+1);
for(int i=1;i<=n;i++) a[i]=s[i]=='('?1:-1;
for(int i=1;i<=n;i++) sum+=a[i];
if(sum!=2&&sum!=-2) return 0*puts("0");
if(sum==-2) {
for(int i=1;i<=n;i++) a[i]*=-1;
for(int l=1,r=n;l<r;l++,r--) swap(a[l],a[r]);
}sum=0;
for(int i=1;i<=n;i++) {
sum+=a[i];if(a[i]>0) ans++;
if(sum<2) ans=0;
if(sum<0) return 0*puts("0");
}
printf("%d
",ans);
return 0;
}
F - Make It Connected
首先我们可以发现，最终答案上的边，要么是题目中给定的，要么就是向权值最小的点连边。因为假设答案中有一条边((u,v))不是题目给定的边，那么边权即为(a_u+a_v)，设权值最小的点为x，因为u和v最终还是要和x所在的联通块连边，那么我们假设是v向该联通块连边，那么u可以向x连边，因为(a_xle a_v),所以向x连边一定不会比向v连边更劣。
那么我们就把所有边以及所有点连向x的边做最小生成树即可。
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int Maxn=1100000;
struct node {
int x,y;
ll w;
node(int u=0,int v=0,ll wi=0) {
x=u;y=v;w=wi;
}
}a[Maxn];
int n,m,f[Maxn];
ll b[Maxn];
int cmp(node a,node b) {
return a.w<b.w;
}
int find(int x) {
if(x!=f[x]) f[x]=find(f[x]);
return f[x];
}
int main() {
scanf("%d%d",&n,&m);
ll temp=0x7fffffffffffffff,ans=0;
int zhy;
for(int i=1;i<=n;i++) {
scanf("%I64d",&b[i]);
if(b[i]<temp) {
zhy=i;
temp=b[i];
}
f[i]=i;
}
for(int i=1;i<=m;i++)
scanf("%d%d%I64d",&a[i].x,&a[i].y,&a[i].w);
for(int i=1;i<=n;i++) a[++m]=node(i,zhy,temp+b[i]);
sort(a+1,a+m+1,cmp);
for(int i=1;i<=m;i++)
if(find(a[i].x)!=find(a[i].y))
f[f[a[i].x]]=f[a[i].y],ans+=a[i].w;
printf("%I64d
",ans);
return 0;
}