首测：220qwq（算差的好吧）
后来改了一个地方：300qwq（算慢的好吧）
std被踩qwq
注意：输入数据第一行忘记输入n，亲脑补
题解：
多项式除法（若最后除出的答案为1那么就是成功），对于f(x)=0的一个解x=e 单项式（x-e）必然是f(x)的一个因式
而解是[1，20]的正整数，那么暴力搜索e的值。就行
AC代码：
# include <bits/stdc++.h>
# define Rint register int
using namespace std;
const int MAXN=;
int r[MAXN],a[MAXN],t[MAXN],n,ans[MAXN],last[MAXN];
inline bool chu(int e)//多项式除法（x-e）
{
memcpy(t,a,sizeof(a));
memset(r,,sizeof(r));
for (Rint i=n;i>=;i--) {
if (t[i]==) continue;
int k=t[i];
r[i-]=k;
t[i]=; t[i-]=t[i-]+k*e;
}
for (Rint i=;i<=n;i++)
if (t[i]!=) return false;
return true;
}
inline void dfs(int x,int tot)
{
if (tot==n) return;
for (Rint i=;i<=;i++) {
if (chu(i)) {
memcpy(last,a,sizeof(a));
memcpy(a,r,sizeof(r));
ans[++ans[]]=i;
dfs(i,tot+);
memcpy(a,last,sizeof(last));
}
}
}
int main()
{
freopen("equation.in","r",stdin);
freopen("equation.out","w",stdout);
scanf("%d",&n);
for (Rint i=;i<=n;i++) scanf("%d",&a[i]);
memset(ans,,sizeof(ans));
dfs(,);
for (Rint i=;i<=n;i++) printf("%d ",ans[i]);
printf("\n");
return ;
}
题解：配对？马上想到二分图。 怎么建图？
加起来是质数那么就连双向边，然后跑一边匈牙利算法，答案除以二就是答案
然而这是针对数字不为0的情况，如果数字为0，那么分奇数偶数考虑
显然 (奇数)+（奇数）!=质数
(偶数)+（偶数）!=质数
左边是奇数右边是偶数，然后加起来是质数连单向边，跑匈牙利算法
这里程序用了第一种方法
# include <bits/stdc++.h>
# define Rint register int
using namespace std;
const int MAXN=;
int n,a[MAXN],pre[MAXN],ans=;
bool mp[MAXN][MAXN],vis[MAXN];
bool prime[];
inline bool is_prime(int x)
{
if (x==) return false;
if (x==) return true;
return prime[x];
}
inline bool find(int u)
{
for (Rint i=;i<=n;i++)
if ((!vis[i])&&(mp[u][i])) {
vis[i]=true;
if (pre[i]==-||find(pre[i])){
pre[i]=u;
return true;
}
}
return false;
}
inline void solve()
{
memset(pre,-,sizeof(pre));
for (Rint i=;i<=n;i++){
memset(vis,false,sizeof(vis));
if (find(i)) ans++;
}
}
inline int read()
{
int X=,w=; char c=;
while(c<''||c>'') {w|=c=='-';c=getchar();}
while(c>=''&&c<='') X=(X<<)+(X<<)+(c^),c=getchar();
return w?-X:X;
}
void getprime(int n)
{
memset(prime,true,sizeof(prime));
for (int i=;i<=n;i++) {
if (prime[i]==false) continue;
for (int j=i+i;j<=n;j+=i) prime[j]=false;
}
}
int main()
{
freopen("prime.in","r",stdin);
freopen("prime.out","w",stdout);
getprime();
scanf("%d",&n);
memset(mp,false,sizeof(mp));
for (Rint i=;i<=n;i++) a[i]=read();
for (Rint i=;i<=n;i++)
for (Rint j=;j<=n;j++)
if ((i!=j)&&(is_prime(a[i]+a[j]))) mp[i][j]=true,mp[j][i]=true;
ans=;
solve();
printf("%d\n",ans/);
return ;
}
题解：和斗地主有几分胜似，暴力dfs是正解（不知道我斗地主会打几行）
句子1 句子2 句子3 句子4 将牌
对于每个句子0表示由三张相同的牌组成，1表示3张花色相同且连续的牌组成
dfs(p1,p2,p3,p4,now)表示句子1，句子2，句子3，句子4的状态是p1,p2,p3,p4（都是0 1），now表示当前的句子是句子now
然后搜索所有状态，判断剩下的牌是不是符合条件就可以了
程序如下
# include <bits/stdc++.h>
using namespace std;
struct node{
char s[];
};
struct qwq{
int hua,num;
}w[];
vector<node>v;
char s[];
int a[][];
bool judge()
{
bool flag=false;
for (int i=;i<=;i++)
for (int j=;j<=;j++)
if (a[i][j]>) if (a[i][j]==) return ;
else return ;
}
bool flag;
void dfs(int p1,int p2,int p3,int p4,int now)
{
if (now==) {
if (judge()) { flag=true;return; }
else return;
}
if (now==) {
if (p1==) {
for (int i=;i<=;i++)
for (int j=;j<=;j++)
if (a[i][j]>=) {
a[i][j]-=;
w[].hua=w[].hua=w[].hua=i;
w[].num=w[].num=w[].num=j;
dfs(p1,p2,p3,p4,now+);
a[i][j]+=;
}
} else {
for (int i=;i<=;i++)
for (int j=;j<=;j++)
if ((a[i][j]>)&&(a[i][j+]>)&&(a[i][j+]>)) {
a[i][j]--;a[i][j+]--;a[i][j+]--;
w[].hua=w[].hua=w[].hua=i;
w[].num=j;w[].num=j+;w[].num=j+;
dfs(p1,p2,p3,p4,now+);
a[i][j]++;a[i][j+]++;a[i][j+]++;
}
}
} else if (now==){
if (p2==) {
for (int i=;i<=;i++)
for (int j=;j<=;j++)
if (a[i][j]>=) {
a[i][j]-=;
w[].hua=w[].hua=w[].hua=i;
w[].num=w[].num=w[].num=j;
dfs(p1,p2,p3,p4,now+);
a[i][j]+=;
}
} else {
for (int i=;i<=;i++)
for (int j=;j<=;j++)
if ((a[i][j]>)&&(a[i][j+]>)&&(a[i][j+]>)) {
a[i][j]--; a[i][j+]--; a[i][j+]--;
w[].hua=w[].hua=w[].hua=i;
w[].num=j;w[].num=j+;w[].num=j+;
dfs(p1,p2,p3,p4,now+);
a[i][j]++;a[i][j+]++;a[i][j+]++;
}
}
} else if (now==){
if (p3==) {
for (int i=;i<=;i++)
for (int j=;j<=;j++)
if (a[i][j]>=) {
a[i][j]-=;
w[].hua=w[].hua=w[].hua=i;
w[].num=w[].num=w[].num=j;
dfs(p1,p2,p3,p4,now+);
a[i][j]+=;
}
} else {
for (int i=;i<=;i++)
for (int j=;j<=;j++)
if ((a[i][j]>)&&(a[i][j+]>)&&(a[i][j+]>)) {
a[i][j]--;a[i][j+]--;a[i][j+]--;
w[].hua=w[].hua=w[].hua=i;
w[].num=j;w[].num=j+;w[].num=j+;
dfs(p1,p2,p3,p4,now+);
a[i][j]++;a[i][j+]++;a[i][j+]++;
}
}
} else if (now==){
if (p4==) {
for (int i=;i<=;i++)
for (int j=;j<=;j++)
if (a[i][j]>=) {
a[i][j]-=;
w[].hua=w[].hua=w[].hua=i;
w[].num=w[].num=w[].num=j;
dfs(p1,p2,p3,p4,now+);
a[i][j]+=;
}
} else {
for (int i=;i<=;i++)
for (int j=;j<=;j++)
if (a[i][j]>&&a[i][j+]>&&a[i][j+]>) {
a[i][j]--;a[i][j+]--;a[i][j+]--;
w[].hua=w[].hua=w[].hua=i;
w[].num=j;w[].num=j+;w[].num=j+;
dfs(p1,p2,p3,p4,now+);
a[i][j]++;a[i][j+]++;a[i][j+]++;
}
}
}
}
bool check()
{
for (int a=;a<=;a++)
for (int b=;b<=;b++)
for (int c=;c<=;c++)
for (int d=;d<=;d++)
{
flag=false;
dfs(a,b,c,d,);
if (flag) return true;
}
return false;
}
int main()
{
freopen("mahjong.in","r",stdin);
freopen("mahjong.out","w",stdout);
for (int i=;i<=;i++) {
scanf("%s",s);
node tmp;
memcpy(tmp.s,s,sizeof(s));
v.push_back(tmp);
}
memset(a,,sizeof(a));
for (int i=;i<v.size();i++) {
if (v[i].s[]=='w') a[][v[i].s[]-'']++;
else if (v[i].s[]=='p') a[][v[i].s[]-'']++;
else if (v[i].s[]=='s') a[][v[i].s[]-'']++;
}
int ansp=,ansnum=;
for (int i=;i<v.size();i++) {
int ch,num;
if (v[i].s[]=='w') ch=;
else if (v[i].s[]=='p') ch=;
else if (v[i].s[]=='s') ch=;
num=v[i].s[]-'';
a[ch][num]--;
int cnt=;
for (int j=;j<=;j++)
for (int k=;k<=;k++)
{
int tt=-a[j][k];
if (tt==) continue;
a[j][k]++;
if (check()) cnt+=tt;
a[j][k]--;
}
if (cnt>ansnum) {
ansnum=cnt; ansp=i+;
}
a[ch][num]++;
}
printf("%d %d\n",ansp,ansnum);
return ;
}