110分
【比赛】2022高考集训3 - 比赛 - 衡中OI (hszxoj.com)
1.单调队列优化DP
#include
#include
#include
#include
#include<string>
#include
#include
#include
#include
#include
#include
2.无脑DP
#include
#include
#include
#include
#include<string>
#include
#include
#include
#include
#include
#include
3.图论的相关知识+思维
学会自己找性质和结论
const int SIZE=400;
const int WR=1001000;
int n,aim[WR];
int ipt[WR];
int lve,sze;
int que[WR],pos;
bool kill[WR],exist[WR];
int main()
{
freopen("maf.in","r",stdin);freopen("maf.out","w",stdout);
n=re();
_f(i,1,n)aim[i]=re(),ipt[aim[i]]++;
_f(i,1,n)
{
if(ipt[i]==0)
{
lve++;que[++sze]=i;
}
}
pos=1;
while(pos<=sze)
{
int frnt=que[pos];//取出那个(起初)一定是不死
pos++;
if(kill[aim[frnt]])continue;//如果不死神的目标死了,走掉
kill[aim[frnt]]=true;
int targ=aim[aim[frnt]];//不死神的目标的目标，目标一定死，目标的目标不一定
ipt[targ]--;//假如目标死了，那targ当前就成了不死神2
exist[targ]=true;//是被救的
if(!ipt[targ])que[++sze]=targ;
}
_f(i,1,n)
{
if(ipt[i]&&!kill[i])
{
int ring=0;
bool flag=false;
for(int j=i;!kill[j];j=aim[j])
{
ring++;
if(exist[j])flag=true;
kill[j]=true;
}
if(!flag&&ring>1)lve++;//排除自环
sze+=ring/2;
}
}
chu("%d %d",n-sze,n-lve);
return 0;
}
4.结论+固定条件+简单唯一枚举
const int SIZE=400;
bool zhen[5][5];
bool fuben[5][5];int tot;
inline void cpy()
{
_f(i,1,4)
{
_f(j,1,4)zhen[i][j]=fuben[i][j];
}
}
char s[5][5];
inline void maketurn(int x,int y)
{
tot++;
zhen[x+1][y]=!zhen[x+1][y];
zhen[x-1][y]=!zhen[x-1][y];
zhen[x][y-1]=!zhen[x][y-1];
zhen[x][y+1]=!zhen[x][y+1];
zhen[x][y]=!zhen[x][y];
}
int minans=INF;
inline bool check(bool p)
{
_f(i,1,4)
{
_f(j,1,4)
if(zhen[i][j]!=p)return false;
}
return true;
}
int main()
{
freopen("flip.in","r",stdin); freopen("flip.out","w",stdout);
_f(i,1,4)
{
scanf("%s",s[i]+1);
int dieC=0;
_f(j,1,4)
{
if(s[i][j]=='w')zhen[i][j]=1,fuben[i][j]=1;
//chu("%d ",zhen[i][j]);
}
// chu("\n");
}
//枚举操作数，如果翻转就是1，不反转就是0
_f(i,0,15)
{
cpy();
tot=0;
//i是操作就要干
_f(j,1,4)
{
if(i&(1<<(j-1)))
{
maketurn(1,j);
}
}
//第一行
_f(j,1,4)
{
if(zhen[1][j]!=0)maketurn(2,j);//先都变成0
}
_f(j,1,4)//第二行
{
if(zhen[2][j]!=0)maketurn(3,j);
}
_f(j,1,4)//第三行
{
if(zhen[3][j]!=0)maketurn(4,j);
}
if(check(0))minans=min(minans,tot);
}
_f(i,0,15)
{
cpy();
tot=0;
//i是操作就要干
_f(j,1,4)
{
if(i&(1<<(j-1)))
{
maketurn(1,j);
}
}
//第一行
_f(j,1,4)
{
if(zhen[1][j]!=1)maketurn(2,j);//先都变成0
}
_f(j,1,4)//第二行
{
if(zhen[2][j]!=1)maketurn(3,j);
}
_f(j,1,4)//第三行
{
if(zhen[3][j]!=1)maketurn(4,j);
}
// chu("isok?\n");
// chu("check:%d\n",check(1));
// chu("minans:%d tot:%d\n",minans,tot);
if(check(1))minans=min(minans,tot);
}
if(minans==INF)chu("Impossible");
else chu("%d",minans);
return 0;
}
/*
枚举的前提是知道性质：
1.当第一行确定翻转，后面的反转方案唯一
2.反转顺序无所谓
3每个点如果反转超过1次即无解
枚举第一行状态
然后
枚举1 2，3 4
x,y==1,必须让x+1,y反转
*/