前言
结束了 也许这几天很苦 但也是最有意义的几天 这篇写简单一点吧
T1 颠倒黑白
很强的构造题
根据打表找出思路
因为最左下角的是一定要点的 就考虑它
- 如果是先手 左下角有黑色 就把它点了 后手只能帮我们把其它黑色点了 最后还是我们先点完
- 若是后手 左下角是白色 与先手同理
一个简单判断即可
#include<bits/stdc++.h>
using namespace std;
int g,n,m,c;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>g;
while(g--)
{
cin>>n>>m;
for(int i=1;i<=n-1;i++)
for(int j=1;j<=m;j++)
cin>>c;
cin>>c;
if(c) cout<<"T\n";
else cout<<"F\n";
for(int j=2;j<=m;j++)
cin>>c;
}
return 0;
}
T2 糖果数 原题
题意：给定一个 \(n\space (n\leq 10^{18})\) 求在 \(n\) 位数以内有多少个包含 \(111\) 的数
推荐我的博客：矩阵快速幂
这题就是原题换了一下 不想说了 容斥一下转为求没有 \(111\) 的数即可
Code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll mod=998244353;
ll n;
struct node{
ll r[4][4];
int n,m;
}ans,a;
node clear(int n,int m)
{
node c;
c.n=n,c.m=m;
memset(c.r,0,sizeof(c.r));
return c;
}
node operator *(node a,node b)
{
node c=clear(a.n,b.m);
for(int i=1;i<=a.n;i++)
for(int k=1;k<=a.m;k++)
for(int j=1;j<=b.m;j++)
c.r[i][j]=(c.r[i][j]+a.r[i][k]*b.r[k][j])%mod;
return c;
}
ll Qpow(ll a,ll x)
{
ll sum=1;
while(x)
{
if(x&1) sum=sum*a%mod;
a=a*a%mod;
x/=2;
}
return sum;
}
node Qpow(node a,ll x)
{
node sum=clear(a.m,a.m);
for(int i=1;i<=a.m;i++)
sum.r[i][i]=1;
while(x)
{
if(x&1) sum=sum*a;
a=a*a;
x/=2;
}
return sum;
}
int main()
{
scanf("%lld",&n);
ans.n=1,ans.m=3;
ans.r[1][1]=9,ans.r[1][2]=1,ans.r[1][3]=0;
a.n=a.m=3;
a.r[1][1]=9,a.r[1][2]=1,a.r[1][3]=0;
a.r[2][1]=9,a.r[2][2]=0,a.r[2][3]=1;
a.r[3][1]=9,a.r[3][2]=0,a.r[3][3]=0;
ans=ans*Qpow(a,n-1);
printf("%lld",(Qpow(10,n)-(ans.r[1][1]+ans.r[1][2]+ans.r[1][3])%mod+mod)%mod);
return 0;
}
T3 天使玩偶 原题
题意：会动态加点 每次询问一个点离另一个点最小的曼哈顿距离
有很多情况 考虑 \(b_x\leq a_x\space b_y\leq a_y\) 的情况 即 \(b\) 在 \(a\) 左下角
那么问题转化为 求
\(a_{tim}\leq b_{tim},{a_x\leq b_x,a_y\leq b_y}\)