CF1093

这场比赛打得很糟心，具体来说就是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;
}