2021.7.16 提高B组模拟赛

$2021.7.16$ 模拟赛$Ⅴ$
目录：

T1.并行博弈
T2.图书馆
T3.小学生语文题
T4.矩形

$T1：$并行博弈

分析：

博弈论
结论$：$左上角是$1$ 先手必胜 否则后手必胜
因为每次选择会翻转左上方左右棋子的颜色 先手改变左上角颜色 后手不管点哪里 左上角颜色一定会被改回去 那么先手就可以一直选择点左上角了

如果是$0$ 先手只能点别的位置 左上角就会变成$1$ 后手就可以一直选择点左上角了
注意$k$盘棋 不是$k$盘棋每盘一个赢家 是两个人下$k$盘棋
用标准$SG$游戏 $ans$全部$xor$上就行了

CODE：

#include
#include
#include
#include
using namespace std;
int T;
int main(){scanf("%d",&T);while(T--){int k,ans=0;scanf("%d",&k);while(k--){int n,m,x,qwq;scanf("%d%d%d",&n,&m,&qwq);for(int i=2;i<=n*m;i++)scanf("%d",&x);ans^=qwq;}(ans)?puts("lyp win"):puts("ld win");}return 0;
}

$T2：$图书馆

分析：

$dp$
f i , j , k f_{i,j,k} fi,j,k​表示第$i$个楼梯 走过$j$个楼梯 消耗$k$体力值的长度平方和
f i , j , k = m i n { f i , j , k , f q w q , j − 1 , k − l e n + l e n 2 } f_{i,j,k}=min\{f_{i,j,k},f_{qwq,j-1,k-len}+len^2\} fi,j,k​=min{fi,j,k​,fqwq,j−1,k−len​+len2} $qwq$为枚举的$i$的起点

最后统计答案 套上$\sigma$简化公式即可

CODE：

#include
#include
#include
#include
#include
#define reg register
using namespace std;
const int N=305;
int n,m,tot,head[N],f[55][55][N<<1];
struct node{int to,next,k;
}a[N];
double ans=0x7fffffff,tmp;
void add(int x,int y,int k)
{a[++tot]=(node){y,head[x],k};head[x]=tot;
} 
int main(){
//	freopen("library.in","r",stdin);
//	freopen("library.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1,x,y,k;i<=m;i++){scanf("%d%d%d",&x,&y,&k);add(y,x,k);}memset(f,0x7f,sizeof f);f[1][0][0]=0;for(reg int j=1;j<=20;j++)for(reg int i=2;i<=n;i++)for(reg int k=0;k<=20*50;k++)for(reg int l=head[i];l;l=a[l].next)	{int qwq=a[l].to,val=a[l].k;if(k<val) continue;f[i][j][k]=min(f[i][j][k],f[qwq][j-1][k-val]+val*val);}for(reg int j=1;j<=20;j++)for(reg int k=0;k<=20*50;k++){tmp=1.0*f[n][j][k]-1.0*k*k/j*1.0;ans=min(ans,fabs(tmp)/j*1.0);}printf("%.4lf",ans);return 0;
} 

$T3：$小学生语文题

分析：

$dp$
设 f i , j f_{i,j} fi,j​表示$A$串$i-n$匹配完成 $B$串用了$j-n$
f i , j f_{i,j} fi,j​的状态只能从 f i + 1 , j , f i , j + 1 , f i + 1 , j + 1 f_{i+1,j},f_{i,j+1},f_{i+1,j+1} fi+1,j​,fi,j+1​,fi+1,j+1​转移过来
要从头一位位确定 前面的好了才能做后面的

$I.$ 转移到 f i + 1 , j + 1 f_{i+1,j+1} fi+1,j+1​ 保证 A i + 1 = B i + 1 A_{i+1}=B_{i+1} Ai+1​=Bi+1​ 匹配数$+1$
$II.$ 转移到 f i + 1 , j f_{i+1,j} fi+1,j​ 匹配数不变 意思是 A i + 1 A_{i+1} Ai+1​与 B j B_j Bj​的后一位相等时再匹配
类似先 A i + 1 A_{i+1} Ai+1​放弃正常匹配 等后面某个 B x B_x Bx​与它相等时再匹配
$III.$ 转移到 f i , j + 1 f_{i,j+1} fi,j+1​ 匹配数不变
也是同$II$ B j + 1 B_{j+1} Bj+1​先放弃正常匹配 等前面某个 A x A_x Ax​与它相等再匹配
这个转移有条件 必须在前面有能与 B j + 1 B_{j+1} Bj+1​匹配的 A x A_x Ax​

最后考虑相对位置 考虑$i$作为答案对$i+1$至$n$的影响 有影响就$+1$即可

CODE：

#include
#include
#include
#include
#pragma GCC optimize(2)
using namespace std;
const int N=2005;
int T,f[N][N],vis[N],num[N][27],num2[N][27],tot[27],tot2[27];
int cnt;
struct qaq{int l,r;
}ans[N],tmp[N][N];
char s[N],s2[N];
int main(){
//	freopen("chinese.in","r",stdin);
//	freopen("chinese.out","w",stdout);scanf("%d",&T);while(T--){scanf("%s",s+1);scanf("%s",s2+1);int len=strlen(s+1); memset(f,0x7f,sizeof f);memset(num,0,sizeof num); memset(num2,0,sizeof num2);memset(tot,0,sizeof tot); memset(tot2,0,sizeof tot2);for(int i=len;i>=1;i--){for(int j=0;j<26;j++)num[i][j]=num[i+1][j],num2[i][j]=num2[i+1][j];num[i][s[i]-'a']++;num2[i][s2[i]-'a']++;}for(int i=1;i<=len+1;i++){f[len+1][i]=len+1-i;tmp[len+1][i]=(qaq){len+1,i+1};}for(register int i=len;i>=1;i--)for(register int j=i;j>=1;j--){f[i][j]=f[i][j+1]+1;tmp[i][j]=(qaq){i,j+1};if(num[i][s[i]-'a']<=num2[j][s[i]-'a']&&f[i+1][j]<f[i][j])f[i][j]=f[i+1][j],tmp[i][j]=(qaq){i+1,j};if(s[i]==s2[j]&&f[i+1][j+1]<f[i][j])f[i][j]=f[i+1][j+1],tmp[i][j]=(qaq){i+1,j+1};}printf("%d\n",f[1][1]);int x=1,y=1;memset(vis,0,sizeof vis);while(f[x][y]){int dl=tmp[x][y].l,dr=tmp[x][y].r;if(x+1==dl&&y==dr)vis[x]=1;x=dl; y=dr;}int k=0,j=len,i=len;cnt=0;while(j){if(s2[i]==s[j]){i--;j--;continue;}if(!vis[j]) f[s2[i]-'a'][++tot[s2[i]-'a']]=i,i--;else{ans[++cnt]=(qaq){f[s[j]-'a'][++tot2[s[j]-'a']],i+1};j--;k++;}}for(register int i=1;i<=cnt;i++)for(register int j=i+1;j<=cnt;j++){if(ans[i].l>ans[j].l&&ans[i].r<ans[j].l) ans[j].l++;if(ans[i].l>ans[j].r&&ans[i].r<ans[j].r) ans[j].r++;}for(int i=1;i<=cnt;i++)printf("%d %d\n",ans[i].l,ans[i].r);}return 0;
}

$T4：$矩形

分析：

正解线段树 扫描线也可以 但我打的是水法
就是看与两条垂直线段相交的水平线段个数$k$
然后 a n s = k ( k − 1 ) 2 ans=\frac{k(k-1)}{2} ans=2k(k−1)​ O ( n 3 ) O(n^3) O(n3)可过

CODE：

#include
#include
#include
#include
#define reg register
using namespace std;
const int N=2005;
struct qaq{int u,v,x,y;
}a[N],b[N];
bool ovo[N][N];
int n,u,v,x,y,tot,tot2,w[N][N],cnt[N],ans,qwq,awa,tmp;
bool check(int l,int x,int r){return l<=x&&x<=r;}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d%d%d",&u,&v,&x,&y);if(y==v){if(u>x) swap(u,x);a[++tot]=qaq{u,v,x,y};}else {if(v>y) swap(v,y);b[++tot2]=qaq{u,v,x,y}; }}for(reg int i=1;i<=tot;i++)for(reg int j=1;j<=tot2;j++)if(check(a[i].u,b[j].u,a[i].x)&&check(b[j].v,a[i].v,b[j].y)){ovo[i][j]=1;w[i][++cnt[i]]=j;}for(reg int i=1;i<tot;i++)for(reg int j=i+1;j<=tot;j++){tmp=0;qwq=i;awa=j;if(cnt[i]>cnt[j]) awa=i,qwq=j;for(int k=1;k<=cnt[qwq];k++)if(ovo[awa][w[qwq][k]])tmp++;ans+=tmp*(tmp-1)/2;}printf("%d",ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！