​​​​​​连接

目录

A:开开心心233

B:Square Game

F:necklace

K:tourist

---

补题中，会给出大部分代码

A:开开心心233

签到题 ，无论二分还是解方程还是直接for循环枚举都能直接通过啦

signed main()
{
	ios_base::sync_with_stdio(0); cin.tie(0),cout.tie(0);
	int n,m;
	cin>>n>>m;
//	cout<<-3+sqrt(3*3+4*2*(n+m))<<'\n';
	int res1=n-(-3+sqrt(3*3+4*2*(n+m)))/2;
	int res2=n-(-3-sqrt(3*3+4*2*(n+m)))/2;
	if(res1<=n&&res1>=0) cout<<res1;
	else cout<<res2;
}
 

B:Square Game

#define f first
#define s second
const int N=1e6+5;
int f[N];
void init()
{
	for(int i=1;i<N;i++){
		int q=sqrt(i);
		map<int,bool>mp;
		if(q*q==i||q*q+1==i){
			for(int j=0;j<i;j+=q){
				mp[f[j]]=1;
			}
			int cnt=0;
			for(auto w:mp){
				if(w.f==cnt) cnt++;
				else break;
			}
			f[i]=cnt;
		}else{
			f[i]=f[i-1];
		}
	}
}
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	init();
	int n;
	cin>>n;
	int sum=0;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		sum^=f[x];
	}
	if(sum==0){
		cout<<"Second\n";
	}else{
		cout<<"First\n";
	}
}

F:necklace

const int inf=0x3f3f3f3f;
int change[410][410];
 
signed main()
{
	ios_base::sync_with_stdio(0); cin.tie(0),cout.tie(0);
	memset(change,0x3f,sizeof change);
	int n,m;
	cin>>n>>m;
	vector<int>s(n),t(n);
	for(int i=0;i<n;i++)
	{
		cin>>s[i];
	}
	for(int i=0;i<n;i++)
	{
		cin>>t[i];
	}
	while(m--)
	{
		int a,b,c;
		cin>>a>>b>>c;
		change[a][b]=min(change[a][b],c);
	}
	for(int k=1;k<=400;k++)
	{
		for(int i=1;i<=400;i++){
			for(int j=1;j<=400;j++){
				change[i][j]=min(change[i][j],change[i][k]+change[k][j]);
			}
		}
	}
	bool ok=0;
	int tot=inf;
	for(int i=0;i<n;i++)
	{
		int sum=0;
		bool flag=1;
		for(int j=0;j<n;j++){
			if(s[j]==t[(i+j)%n]) continue;
			int p=inf;
			p=min(change[s[j]][t[(i+j)%n]],p);
			p=min(change[t[(i+j)%n]][s[j]],p);
			if(p>=inf){
			flag=0;
			break;				
			}
			sum+=p;
		}
		if(flag==0){
//			ok=0;
//			break;
		}else{
			ok=1;
			tot=min(tot,sum);
		}
	}
	if(!ok){
		cout<<-1<<'\n';
	}else{
		cout<<tot<<'\n';
	}
}

K:tourist

#define int long long
const int K=1<<7,mod=1e9+9;
int path[21][21];
int st[K];
int sz[10];
int siz(int x) {
	int cnt=0;
	while(x) {
		if(x&1) cnt++;
		x>>=1;
	}
	return cnt;
}
int a[21][21];
int f[21];
int n,m,k,d;
void mul(int f[],int a[21][21]) {
	int c[21]= {0};
	for(int j=1; j<=n; j++) {
		for(int k=1; k<=n; k++) {
			c[j]=(c[j]+f[k]*a[k][j])%mod;
		}
	}
	memcpy(f,c,sizeof c);
}
void mulself(int a[21][21]) {
	int c[21][21]= {0};
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			for(int k=1; k<=n; k++) {
				c[i][j]=(c[i][j]+a[i][k]*a[k][j])%mod;
			}
		}
	}
	memcpy(a,c,sizeof c);
}
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>k>>d;
	d--;
	for(int i=0; i<k; i++) {
		int x;
		cin>>x;
		st[(1ll<<i)]=x;
	}
	while(m--) {
		int u,v;
		cin>>u>>v;
		path[u][v]=1;
		path[v][u]=1;
	}
	for(int i=0; i<(1ll<<k); i++) {
		int size=siz(i);
		memcpy(a,path,sizeof path);
		for(int j=0; j<k; j++) {
			if((i>>j)&1) {
				int p=st[(1ll<<j)];
				for(int k=1; k<=n; k++) {
					a[p][k]=0;
					a[k][p]=0;
				}
			}
		}
		for(int ii=1; ii<=n; ii++) {
			f[ii]=1;
		}
		int dd=d;
		for(; dd; dd>>=1) {
			if(dd&1) mul(f,a);
			mulself(a);
		}
		for(int j=1; j<=n; j++) {
			sz[size]+=f[j];
			sz[size]%=mod;
		}
	}
	int sum=0;
	for(int i=0; i<=k; i++) {
		if(i%2==0) {
			sum+=sz[i];
			sum%=mod;
		} else {
			sum=(sum-sz[i]+mod)%mod;
		}
	}
	cout<<sum<<'\n';
}