2024杭电5

题意：
有n个灯，开始时全部是关闭状态。
选连续3个开关（左右边界不用选满），改变它的状态。
任意操作次数，问一共可以有多少种状态。

题解：
暴力找规律，发现$n\mathrm{mod}3=2$时是$2^{n-1}$
其他都是$2^n$

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+6;
const int mod=998244353;
int ksm(int a ,int k) //a代表底数，k代表大指数
{
    int rec = 1;
    while(k)
    {
        if (k & 1)
            rec = rec * a % mod;
        k >>= 1;
        a = a * a % mod;
    }
    return rec;
}
void solve()
{
	int n;
	cin>>n;
	if(n==1||n==2){
		cout<<"2\n";
		return ;
	}
	if(n%3==2){
		n--;
	}
	int ans=ksm(2,n);
		ans=ans*2%mod;
	cout<<ans<<'\n';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

题意：
有三堆罐头$a,b,c$，小小猫和勇者猫操作：
选两堆罐头，其中一个吃光，剩下那堆分为两堆非空的两堆。
无法操作的猫输，问谁可以比赛。

题解：
最终的必败态情况$1,1,1$.
一个奇数堆要分为奇数堆和偶数堆，偶数堆可以分为两堆奇数堆。

情况1：$a,b,c$都是奇数
先手必须分成奇数和偶数，后手再把奇数吃掉，把偶数分为两个奇数，最后就会是$1,1,1$,所以全是奇数先手必败。

情况2：$a,b,c$有奇数有偶数
假如有一个偶数，先手必胜，已经在情况1说了。
假如有两个偶数，先手吃掉一个偶数，把另外一个偶数分为奇数+奇数，也是先手必胜。
有奇数偶数都是先手必胜。

情况3：$a,b,c$都是偶数
$2,2,2$先手必败
一个数是4的倍数，那就可以分为两个偶数，所以最后就是看谁可以保持3个偶数，假如谁把偶数分为奇数+奇数就输了。

所以可以一直把3个数字/2，直到出现奇数。
有奇数偶数就先手必胜，否则就是先手必败。

代码：

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+6;
int a[5];
void solve()
{

	for(int i=1;i<=3;i++){
		cin>>a[i];
	}
	while(1){
		if(a[1]%2==0&&a[2]%2==0&&a[3]%2==0){
			a[1]/=2;
			a[2]/=2;
			a[3]/=2;
		}else break;
	}
	
	int f1=0,f2=0;
	for(int i=1;i<=3;i++){
		if(a[i]%2!=0){
			f1=1;
		}
	}
	for(int i=1;i<=3;i++){
		if(a[i]%2==0){
			f2=1;
		}
	}
	if(f1&&f2){
		cout<<"YES\n";
		return ;
	}

	cout<<"NO\n";
	return ;


}
signed main()
{
//    ios::sync_with_stdio(false);
//    cin.tie(0); cout.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

题意：
给定一个长度为$n$的数组，每个元素都大于0。可以进行以下两种操作操作：
· 选$i,j(i\ne j)$，使$a_i=a_{i}mod{a}_j$
· 选$i,x$，使$a_i=a_i+x$
问使数组变为恰好只剩一个非0元素，其余都是0的最少操作数。

题解：
n个数字，n-1个数字变为0，最少需要n-1步。
任何数%1是0，把一个数变为1最多需要2步，所以最多需要n+1步。
所以答案只有3种可能性，$n-1,n,n+1$
情况1：
排序后，所有数%$a_1$都是0，只要n-1步。

情况2：
答案为n的时候，除去n-1个把元素变为0的操作，只有1次操作。
因为$n<=100$我们可以枚举每种情况，对每个元素进行两种操作之一。
(1)使$a_j=a_i$ % $a_i$,这个操作可以最开始就做。

(2)使$a_i=a_i+x$，不一定是最开始就做，可以除去一步变为0的数字，看剩下的gcd是不是大于a[1]。这样可以让$a[1]+x=gcd$。

代码：

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e6;
int a[N];

void solve()
{
	int n,p;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	sort(a+1,a+n+1);
	int f=1;
	for(int i=2;i<=n;i++){
		if(a[i]%a[1]!=0)f=0;
	}
	if(f){
		cout<<n-1<<'\n';
		return ;
	}
	
	f=1;
	for(int i=2;i<=n;i++){

		int g=a[1];
		for(int j=2;j<=n;j++){
			if(j==i)continue;
			g=__gcd(g,a[j]);
		}
		for(int j=i-1;j>=1;j--){
			p=a[i]%a[j];
			if(p==0||p>a[1])continue;
			if(g%p==0){
				cout<<n<<'\n';
				return ;
			}
		}
	}
	
	int d=0;
	for(int i=2;i<=n;i++){
		if(a[i]%a[1])d=__gcd(d,a[i]);
	}
	if(d==0||d>=a[1]){
		cout<<n<<"\n";
		return ;
	}
	
	
	
	cout<<n+1<<'\n';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}