考挂了。。
A - Definite Game
直接看代码吧。
#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;
const int inf=0x7fffffff;
int main() {
int x;
scanf("%d",&x);
if(x==2) puts("2");
else puts("1");
return 0;
}
B - Farewell Party
直接模拟分组即可。
#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;
const ll mod=998244353;
const int inf=0x7fffffff;
int n,a[Maxn],b[Maxn],c[Maxn];
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
b[i]=n-a[i];
}
sort(b+1,b+n+1);b[n+1]=-1;
int temp=1;
while(temp<=n) {
int cnt=1;
while(b[temp]==b[temp+1]) temp++,cnt++;
if(cnt%b[temp]) {
puts("Impossible");
return 0;
}
temp++;
}
int cnt=0;memset(b,0,sizeof(b));
for(int i=1;i<=n;i++) {
int x=n-a[i];
if(b[x]==0)
c[x]=a[i]=++cnt;
b[x]=(b[x]+1)%x;
a[i]=c[x];
}
puts("Possible");
for(int i=1;i<=n;i++) printf("%d ",a[i]);
return 0;
}
C - Colorful Bricks
可以n方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=610000;
const ll mod=998244353;
const int inf=0x7fffffff;
int f[2100][2100],n,m,k;
int main() {
scanf("%d%d%d",&n,&m,&k);
f[1][0]=m;
for(int i=1;i<n;i++)
for(int j=0;j<=k;j++) {
f[i+1][j]=(f[i+1][j]+f[i][j])%mod;
f[i+1][j+1]=(f[i+1][j+1]+1ll*f[i][j]*(m-1)%mod)%mod;
}
printf("%d",f[n][k]);
return 0;
}
D - Maximum Distance
先求最小生成树，然后拓扑排序，有标记的k个点不能删，最后的答案全部一样，就是剩下的边里面的最大值。
#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;
const ll mod=998244353;
const int inf=0x7fffffff;
int to[Maxn],nxt[Maxn],first[Maxn],tot=1,f[Maxn];
int w[Maxn],n,m,b[Maxn],ans,k,bj[Maxn],d[Maxn];
queue<int> q;
struct node {
int u,v,wi;
}a[Maxn];
int cmp(node a,node b) {
return a.wi<b.wi;
}
int find(int x) {
if(f[x]!=x) f[x]=find(f[x]);
return f[x];
}
inline void add(int u,int v,int wi) {
to[tot]=v;
w[tot]=wi;
nxt[tot]=first[u];
first[u]=tot++;
to[tot]=u;
w[tot]=wi;
nxt[tot]=first[v];
first[v]=tot++;
}
void dfs(int root,int fa) {
for(int i=first[root];i;i=nxt[i]) if(to[i]!=fa&&bj[to[i]]!=-1) {
ans=max(ans,w[i]);
dfs(to[i],root);
}
}
int main() {
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=k;i++) scanf("%d",&b[i]),bj[b[i]]=1;
for(int i=1;i<=m;i++)
scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].wi);
sort(a+1,a+m+1,cmp);
for(int i=1;i<=m;i++)
if(find(a[i].u)!=find(a[i].v)) {
add(a[i].u,a[i].v,a[i].wi);
f[f[a[i].u]]=f[a[i].v];
d[a[i].u]++;
d[a[i].v]++;
}
for(int i=1;i<=n;i++)
if(d[i]==1&&!bj[i])
q.push(i),bj[i]=-1;
while(!q.empty()) {
int now=q.front();q.pop();
for(int i=first[now];i;i=nxt[i]) {
d[to[i]]--;
if(d[to[i]]==1&&!bj[to[i]]) {
q.push(to[i]);
bj[to[i]]=-1;
}
}
}
dfs(b[1],b[1]);
for(int i=1;i<=k;i++) printf("%d ",ans);
return 0;
}
E - Missing Numbers
大概就是前几个数的和为完全平方数，而这个数当然越小越好，因为奇数位置可以随意指定，那么前面的和小，一定不会更劣。
然而我当时没开long long ，还过了pretest，所以就愉快地。。
#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;
const ll mod=998244353;
const int inf=0x7fffffff;
bool check(ll x) {
ll y=sqrt(x);
return y*y==x;
}
int n;
ll a[Maxn],b[Maxn],tot;
int main() {
scanf("%d",&n);
for(int i=1;i<=n/2;i++) scanf("%I64d",&a[i]);
ll temp=1;
while(!check(temp*temp+a[1])&&temp<1100000) temp++;
if(temp==1100000) {
puts("No");
return 0;
}
b[++tot]=temp*temp;b[++tot]=a[1];temp=sqrt(temp*temp+a[1]);
for(int i=2;i<=n/2;i++) {
if(temp==1100000) break;ll sxz=temp;temp++;
while(!check(temp*temp+a[i])&&temp<1100000) temp++;
b[++tot]=temp*temp-sxz*sxz;
b[++tot]=a[i];
temp=sqrt(temp*temp+a[i]);
}
if(temp==1100000) {
puts("No");
return 0;
}
puts("Yes");
for(int i=1;i<=n;i++) printf("%I64d ",b[i]);
return 0;
}
于是在打了三场之后，我的rating又回到了原点。。。