这场比赛打得很糟心，具体来说就是Debug能力不足。勉强涨了一点分。
CF1093 A
一道水题。依照题意模拟即可。
#include<iostream>
#include<cstdio>
int n;
void init(){
scanf("%d",&n);
int x,ans;
for(int i=1;i<=n;++i){
scanf("%d",&x);
ans=x/7+1;
printf("%d\n",ans);
}
}
int main(){
init();
return 0;
}
CF1093 B
将字符串排序之后，如果第一项和最后一项不同，那它肯定不是回文；如果相同，那么中间也都相同，判一下即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
int n,len;
char ch[1005];
void init(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
std::memset(ch,0,sizeof(ch));
std::cin>>ch+1;
len=std::strlen(ch+1);
std::sort(ch+1,ch+1+len);
if(ch[1]==ch[len]){
puts("-1");
continue;
}else{
puts(ch+1);
}
}
}
int main(){
init();
return 0;
}
CF1093 C
考虑到数列单调不减，则A序列的前半部分也单调不减，那么我们维护一个值表示当前值，然后从\(1\)扫到\(\frac{n}{2}\)即可。该增加的时候就增加。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
int n;
long long a[200005],b[200005];
void init(){
scanf("%d",&n);
for(int i=1;i<=(n>>1);++i){
scanf("%I64d",b+i);
}
long long nw=0;
for(int i=1;i<=(n>>1);++i){
if(i>1&&b[i]-nw>b[i-1]-a[i-1]){
nw=b[i]-b[i-1]+a[i-1];
}
a[i]=nw,a[n-i+1]=b[i]-nw;
}
for(int i=1;i<=n;++i){
printf("%I64d ",a[i]);
}
}
int main(){
init();
return 0;
}
CF1093 D
考虑每一个连通块各自独立，所以分别计算出值然后乘一起即可。
又，我们发现，本质上题目要求的就是一条线段两端的点的权值的奇偶性不同。
所以我们可以对一个连通块二染色，使得任意两种颜色不相邻。很容易可以证明，要么没有方案，要么方案只有一种。
我们分别考虑用一和三来填充黑色和白色，方案数很显然是\(2^{size_0}+2^{size_1}\)。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
const long long MOD = 998244353;
struct ee{
int v;
int nxt;
}e[600005];
int h[300005],et=0;
inline long long pw(int A,int X){
long long RT=1,BS=A;
while(X){
if(X&1){
RT*=BS;
RT%=MOD;
}
BS*=BS;
BS%=MOD;
X>>=1;
}
return RT;
}
inline void add(int u,int v){
e[++et]=(ee){v,h[u]};
h[u]=et;
}
bool clr[300005],vis[300005];
std::queue<int> q;
struct data{
int A;
int SZ;
};
inline data slv(int X){
int RT=0;
clr[X]=0,vis[X]=1;
while(!q.empty()){
q.pop();
}
q.push(X);
int P,SZ=0;
while(!q.empty()){
P=q.front();
q.pop();
++SZ;
if(!clr[P]){
++RT;
}
for(int i=h[P];i;i=e[i].nxt){
if(vis[e[i].v]){
if(clr[e[i].v]==clr[P]){
return (data){-1,-1};
}
}else{
vis[e[i].v]=1;
clr[e[i].v]=clr[P]^1;
q.push(e[i].v);
}
}
}
return (data){RT,SZ};
}
int n,m;
void init(){
scanf("%d%d",&n,&m);
int u,v;
for(int i=1;i<=m;++i){
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
long long ans=1;
data A;
for(int i=1;i<=n;++i){
clr[i]=0;vis[i]=0;
}
for(int i=1;i<=n;++i){
if(vis[i]){
continue;
}else{
A=slv(i);
if(A.A==-1){
puts("0");
return;
}
ans*=(pw(2,A.SZ-A.A)+pw(2,A.A));
ans%=MOD;
}
}
ans%=MOD;
printf("%I64d\n",ans);
}
inline void CLEAR(){
for(int i=1;i<=et;++i){
e[i].v=e[i].nxt=0;
}
for(int i=1;i<=n;++i){
h[i]=0;
}
n=0,m=0,et=0;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
init();
CLEAR();
}
return 0;
}
