求助ABC的F
  • 板块灌水区
  • 楼主Eric998
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/11/19 21:44
  • 上次更新2023/10/27 02:18:07
查看原帖
求助ABC的F
678534
Eric998楼主2022/11/19 21:44

刚刚结束的ABC,F挂两个点求调

#include <iostream>
#include <vector>
#include <map>
#include <math.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <time.h>
using namespace std;
#define inf 0x3f3f3f3f
#define minf 0x3f
#define inp(x) cin>>x
#define otp(x) cout<<x
#define otp_nl(x) cout<<x<<"\n"
#define otp_sp(x) cout<<x<<" "
#define int long long
#define veci vector<int>
#define str string
#define pb(x) push_back(x)
#define fr(k,len) for(k=0;k<len;k++)
#define nfr(k,len) for(int k=0;k<len;k++)
#define ret return
#define db long double
#define all(x) x.begin(),x.end()

namespace my_stl {

}
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

int qpow(int a, int t, int p) {
	a %= p;
	int b[64];
	b[0] = a;
	nfr(i, 63)b[i + 1] = (b[i] * b[i]) % p;
	int ans = 1;
	nfr(i, 64) {
		if (t & (1 << i)) {
			ans *= b[i];
			ans %= p;
		}
	}
	ret ans;
}

int gcd(int a, int b) {
	ret (b ? (gcd(b, a % b)) : a);
}

int invp(int a, int p) {
	ret qpow(a, p - 2, p);
}
int x, y;

void exgcd(int a, int b, bool f) {
	if (f)
		x = 0, y = 0;
	if (!b) {
		x = 1;
		y = 0;
		return;
	}
	exgcd(b, a % b, false);
	int tx = x;
	x = y;
	y = tx - a / b * y;
}

int inv(int a, int p) {
	exgcd(a, p, true);
	return (x + p) % p;
}
int wn[65536][16];
int ok[65536][16];
vector<string> vs;
int n;
int dfs(int i,int j){// cout<<i<<' '<<j<<' '<<wn[i][j]<<endl;
	if(ok[i][j])return wn[i][j];
	ok[i][j]=1;
	if(i==(1<<n)-1)return wn[i][j]=0;
	int ans=0;
 	int flg=0;
	for(int m=0;m<n;m++){
		if(!((1<<m)&i)){
			if(vs[m][0]==vs[j][vs[j].size()-1]){
              flg=1;
				ans|=dfs(i|(1<<m),m);
			}
		}
	}
  	wn[i][j]=1-ans;
  	if(!flg)wn[i][j]=0;
 
	return wn[i][j];
}
void solve() {
	//int n;
	cin>>n;
	nfr(i,n){
		string s;
		cin>>s;
		vs.push_back(s);
      //cout<<s<<endl;
	}
	for(int i=0;i<n;i++){
		if(dfs(0,i)){
			cout<<"First";
			ret;
		}
	}
	cout<<"Second";
	ret;
}

signed main() {
	int t = 1;
	nfr(i, t) {
		solve();
	}
	ret 0;
}
2022/11/19 21:44
加载中...