2019 CCPC秦皇島現場試合問題解

D:

#include
using namespace std;
const int times = 1e4;
bool is[110];

bool check(int x){
	int res = 1,cnt = 0;
	while(res % x){
		if(res < x)	res *= 10;
		else	res %= x;
		cnt++;
		if(cnt > times)	return false;
	}
	return true;
}

int main(){
	int T,n;
	
	for(int i = 1;i <= 100;++i)	is[i] = check(i);
	cin>>T;
	while(T--){
		cin>>n;
		if(!is[n])	cout<

F:

#include
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 10;
const int maxm = 5e5 + 10;
const int mod = 998244353;

vector e[maxn];
int vis[maxn],table[maxm],no[maxn],cnt;
ll ans;

void dfs(int now,int u,int f){
	vis[u] = 1;no[u] = now;
	for(int i = e[u].size() - 1;i >= 0;i--){
		int v = e[u][i];
		if(v == f)	continue;
		if(!vis[v])	dfs(now + 1,v,u);
		else if(now > no[v]){
			ans = ans * (ll)(table[now - no[v] + 1] - 1) % mod;
			cnt = cnt - (now - no[v] + 1);
		}
	}
}

void gettable(){
	table[0] = 1;
	for(int i = 1;i < maxm;++i)	table[i] = table[i - 1] * 2 % mod;
}

int main(){
	int n,m;
	gettable();
	
	scanf("%d%d",&n,&m);
	
	ans = 1;
	if(m == 0)	printf("1
");
	else{
		cnt = m;
		for(int i = 0;i < m;++i){
			int u,v;
			scanf("%d%d",&u,&v);
			e[u].push_back(v);
			e[v].push_back(u);
		}
		for(int i = 1;i <= n;++i)
			if(!vis[i])	dfs(0,i,0);
		ans = ans * ll(table[cnt]) % mod;
		printf("%lld
",ans);
	}
	
	return 0;
}

I:

#include
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 0x7f7f7f7f;
string str[10][6];
int dis[70][70];
char comba[][3] = {{'Q','Q','Q'},{'Q','Q','W'},{'Q','Q','E'},{'W','W','W'},{'Q','W','W'},{'W','W','E'},{'E','E','E'},{'Q','E','E'},{'W','E','E'},{'Q','W','E'}};
int vis[3],tot;
map M;

void dfs(int deep,string tmp,int t){
	if(deep == 3){
		str[t][tot++] = tmp;
		return;
	}
	
	for(int i = 0;i < 3;++i)
		if(!vis[i]){
			vis[i] = 1;
			dfs(deep + 1,tmp+comba[t][i],t);
			vis[i] = 0;
		}
}

void getdis(){
	for(int i = 0;i < 10;++i){
		tot = 0;
		dfs(0,"",i);
	}
	
	for(int i = 0;i < 10;++i)
		for(int j = 0;j < 10;++j)
			for(int k = 0;k < 6;++k)
				for(int l = 0;l < 6;++l){
					int u = i * 6 + k,v = j * 6 + l;
					if(str[i][k] == str[j][l])	dis[u][v] = 0;
					else if(str[i][k][1] == str[j][l][0] && str[i][k][2] == str[j][l][1]) dis[u][v] = 1;	
					else if(str[i][k][2] == str[j][l][0]) dis[u][v] = 2;
					else dis[u][v] = 3;	
				}
	
	M['Y'] = 0;M['V'] = 1;M['G'] = 2;M['C'] = 3;M['X'] = 4;M['Z'] = 5;M['T'] = 6;M['F'] = 7;M['D'] = 8;M['B'] = 9;
}

int dp[maxn][6];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	getdis();
				
	string str;
	while(cin>>str){
		int len = str.size();
		memset(dp,0x7f,sizeof(dp));
		for(int i = 0;i < 6;++i)	dp[0][i] = 3;
		for(int i = 1;i < len;++i)
			for(int j = 0;j < 6;++j)
				for(int k = 0;k < 6;++k)
					dp[i][j] = min(dp[i][j],dp[i - 1][k] + dis[M[str[i - 1]] * 6 + k][M[str[i]] * 6 +j]);
					
		int ans = inf;
		for(int i = 0;i < 6;++i)	ans = min(dp[len - 1][i],ans);
		cout<< ans + len <

J:

#include
using namespace std;
typedef long long ll;
const ll inf = 0x7f7f7f7f7f7f7f7f;
const int maxn = 1e7 + 10;
char str[maxn];
int Next[maxn];

void getNext(){
	int len = strlen(str);
	Next[len - 1] = -1;
	int i = len - 1,j = -1;
	while(i >= 0){
		if(j == -1 || str[i] == str[len - j - 1]){
			--i,++j;
			Next[i] = j;
		}else
			j = Next[len - j - 1];		
	}
}

int main(){
	ll a,b;
	
	while(~scanf("%lld%lld",&a,&b)){
		scanf("%s",str);
		getNext();
		
		int len = strlen(str);
		ll ans = -inf;
		for(int i = len - 1;str[i] != '.';--i)
			ans = max(ans,a * (len - i) - b * (len - i - Next[i - 1]));
		printf("%lld
",ans);
	}
	
	return 0;
}

残りの問題はあとで補う