题面
T1
一道数学(博弈论)
分析
先手搓几个数据，找找规律，除非个数为1，其余的一旦先手先选，那一定先手获胜，反之必败 那只用统计1的个数即可，但如果全是1，需要特判
#include<cstdio>
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
int T,n,a,ans,tmp=1;
signed main()
{
scanf("%lld",&T);
for(int i=1;i<=T;i++)
{
scanf("%lld",&n);
ans=0;
for(int j=1;j<=n;j++)
{
scanf("%lld",&a);
if(a==1) ans++;
}
if(ans==n)
{
if(n&1) printf("Yes\n");
else printf("No\n");
}
else
{
if(ans&1) printf("No\n");
else printf("Yes\n");
}
}
return 0;
}
T2
一道搜索，记忆化，状压题
分析
看码
点击查看代码
#include<bits/stdc++.h>
#define nt long long
#define maxn 100010
#define N (1<<22)+114514
using namespace std;
int n,x[maxn],y[maxn],vis[maxn],tmp[maxn],ans[maxn],dis[50][50],Ans=(1<<25);
int dp[N];
int calc(int u,int v){return abs(x[u]-x[v])*abs(x[u]-x[v])+abs(y[u]-y[v])*abs(y[u]-y[v]);}
void init()
{
for(int i=0;i<n;i++)
for(int j=i+1;j<=n;j++)
dis[i][j]=dis[j][i]=calc(i,j);// 求出每个点见距离
memset(dp,127,sizeof dp);
}
void DFS(int pos,int now,int idx,int wow)// 当前位置 当前价值 答案序列长度 状态
{
if(now>=Ans||now>=dp[wow]) return ;// 记忆化 如果当前价值大于最终的答案或大于原来的更优状态 回溯
if(vis[pos])
{
DFS(pos+1,now,idx,wow);// 当前已经被标记则跳过
return ;
}
if(pos>n)// 记录答案
{
if(Ans>now)
{
Ans=now;
for(int i=1;i<=n;i++) ans[i]=tmp[i];
}
return ;
}
tmp[idx+1]=pos;
DFS(pos+1,now+2*(dis[0][pos]),idx+1,wow+(1<<pos));// 单走一个六
for(int i=pos+1;i<=n;i++)
{
if(vis[i]) continue;
vis[i]=1;// 标记为选过（为三角形情况）
tmp[idx+2]=i;
DFS(pos+1,now+dis[pos][i]+dis[0][i]+dis[0][pos],idx+2,wow+(1<<pos)+(1<<i));// 对子
vis[i]=0;// 回溯
}
dp[wow]=now;// 记忆化
}
signed main()
{
// Ans=(1<<31)
scanf("%lld%lld",&x[0],&y[0]);
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld%lld",&x[i],&y[i]);
init();// 预处理
DFS(1,0,0,0);
printf("%lld\n",Ans);
for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
return 0;
}
/*
122 116 20
12 34
166 166
56 131
114 76
22 115
15 85
5 9
92 195
154 135
64 200
105 19
122 127
187 157
112 159
162 34
140 155
113 56
148 54
55 140
129 86
145168
1 7 2 13 3 19 4 20 5 6 8 10 9 16 11 17 12 14 15 18
*/