T1 生日快乐
题目传送门
虽然是水题，但很容易被误导成二分，没有证明的直觉不是直觉，但是题目没有卡这种错误的做法
拿了\(70pts\)，和二分相近，只不过每次将所有可能的情况都分出来
也就是说 ， 因为只能平行与两边进行切，所以每次\(DFS\)时将可能出现的情况枚举即可
点击查看代码
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int n;
double x,y,ans=1e9;
double dfs(double x,double y,int d)
{
if(x<y) swap(x,y);
// cout<<x<<" "<<y<<" "<<d<<endl;
if(d==1)
{
return x/y;
}
double mx=x/d,my=y/d,ans=1e9;// 每次在搜索时更新ans值，不能使用全局，每种方法都有不同分法
double ans1,ans2;
for(int i=1;i<=d/2;i++) // 以单位块增加 即枚举所有切法
{
ans1=max(dfs(mx*i,y,i),dfs(x-mx*i,y,d-i));// 沿着x 方向切 i块 与tot-i块
ans2=max(dfs(x,my*i,i),dfs(x,y-my*i,d-i));
ans=min(ans,min(ans1,ans2));
}
return ans;
}
signed main()
{
// freopen("happy.in","r",stdin);
// freopen("happy.out","w",stdout);
scanf("%lf%lf%ld",&x,&y,&n);
;
printf("%.6f",dfs(x,y,n));
return 0;
}
T2 最远距离
题目传送门
这个题意也有点日龙，意思就是一个点可以通过上下左右方向且不被阻挡到达最远的另一个点
然后求出两点间直线距离
虽然题面上是说最远距离，但我们不妨转化为一个最短路问题；
\(dis[i][j]\)表示从某一点到\((i,j)\)所需要移动的障碍
因为数据很小可以用\(SPFA\)水过
然后每次枚举起始点，再枚举终止点，记录直线距离最大值；
点击查看代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
int n,m,t;
int dx[4]={0, 0, 1, -1}, dy[4]={1, -1, 0, 0};
struct node{int x,y;};
node make(int x,int y)
{
node st; st.x=x; st.y=y;
return st;
}
bool ck(int x,int y)
{
if(x<=0 || x>n || y<=0 || y>m) return false;
return true;
}
int dis[50][50],G[50][50],vis[50][50];
int X,Y;
void spfa(int x, int y)
{
queue<node>q;
memset(dis, 127, sizeof dis);
dis[x][y]=G[x][y];
node st;
q.push(make(x,y));
while (q.size())
{
int xx=q.front().x, yy=q.front().y;
vis[xx][yy]=false;
q.pop();
for (int i=0; i<4; i++)
{
X=xx+dx[i]; Y=yy+dy[i];
if (!ck(X,Y)) continue;
if (dis[X][Y]>dis[xx][yy]+G[X][Y])
{
dis[X][Y]=dis[xx][yy]+G[X][Y];
if (!vis[X][Y])
{
q.push(make(X, Y));
vis[X][Y]=true;
}
}
}
}
}
char s[50];
double ans;
signed main()
{
// freopen("dis.in","r",stdin);
// freopen("dis.out","w",stdout);
scanf("%ld%ld%ld",&n,&m,&t);
for(int i=1;i<=n;i++)
{
cin>>s+1;
for(int j=1;j<=m;j++)
{
G[i][j]=(s[j]=='1');
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
spfa(i,j);
for(int x=1;x<=n;x++)
{
for(int y=1;y<=m;y++)
{
if(dis[x][y]<=t)
ans=max(ans,sqrt(abs(x-i)*abs(x-i)+abs(y-j)*abs(y-j)));
}
}
}
}
printf("%.6f\n",ans);
return 0;
}
T3 windy数
题目传送门
妥妥的数位\(DP\)题，用的记忆化搜索，详情见代码
点击查看代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define int long long
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int s[30],dp[30][30];
int dfs(int pos, int pre, int f, int lim )// 当前位数 原先上一位数 是否有前导0 是否有最高位限制
{
if(!pos)return 1;// 如果已经没有数位可以枚举了 返回 1
if(!f && dp[pos][pre] != -1 && !lim) return dp[pos][pre];// 记忆化搜索 如果没有前导0 并且当前值已经存在 并且没有最高位限制
int up = lim ? s[pos] : 9;// 最高位限制判断
int ans = 0;
for(int i=0;i<=up;i++) // 枚举位数上的可能情况
{
int tmp=abs(pre-i);
if(!f && tmp < 2 )continue;// 判断是否合法
ans+=dfs( pos-1, i, f&&!i, lim&&i==up );// 继续搜索下一位 记录当前位（即下一次搜索的pre） 看是否还有前导0 与最高位限制
}
if(!lim && !f)dp[pos][pre] = ans;// 记忆化搜索 记录答案
return ans;
}
int solve(int x)
{
int cnt=0;
memset(s,0,sizeof s);
while(x)
{
s[++cnt]=x%10;
x/=10;
}
return dfs(cnt,-1,1,1);// 因为上一位不存在 所以最高位只要在1~最高位之间
}
int n,m;
signed main()
{
// freopen("windy.in","r",stdin);
// freopen("windy.out","w",stdout);
scanf("%ld%ld",&n,&m);
memset(dp,-1,sizeof dp);
printf("%lld",solve(m)-solve(n-1));
return 0;
}
T4 GT考试
题目传送门
因为有了上一道数位\(DP\)，所以这一道也想数位\(DP\)，然后就挂了
分析
首先 ，看到匹配，显然可以 \(kmp\) 解决
然后 ，是求方案数，显然可以 \(DP\) 递推
怎么递推？？不会力
在上了个厕所，遭遇宇宙射线后，我们知道了答案
\(dp[i][j]\)表示当前在第 \(i\) 位时，末尾已经匹配了 \(j\) 位不吉利串
显然答案最后为\(dp[n][j]=\sum_{k=0}^{m-1}dp[n-1] [k]\)
再看转移\(dp[i]\)是由\(dp[i-1]\)在添加一个数后转移，
添加一个数后会有三种情况
1.当前数位又向着不吉利串更近一步（成功匹配到了下一位成为一段更长的不吉利子串，如12121 为121变为1212）
2.摆脱不吉利串(失配如 1111 变为 1112)
3.摆脱但没完全摆脱(如从1211变为1212，后面的12有可能变为1211)
这就需要\(kmp\)进行维护
用一个\(fail[i][j]\)记录从不吉利串 \(i\) 位匹配到 \(j\) 位的方案数
比如\(12\)到\(121\)（\(fail[2][3]=1\)）只可能一种情况
如\(12\) 到 \(1\) (\(fail[2][1]=9\))会有\(9\)种可能
所以\(dp[i][j]=\sum_{k=0}^{m-1}dp[n-1] [k]+fail[k][j]\)
然后发现\(i\)居然达到了惊人的 \(10^9\)
显而易见，请出矩阵加速
\(dp[i][j]=\sum_{k=0}^{m-1}dp[n-1] [k]+fail[k][j]\)
这不就是一个矩阵乘法的式子吗... 因为\(fail[i][j]\)是固定的，于是把\(f[i][j]\)看成一个矩阵，对于矩阵\(dp[i]\)它的第一层就是\(dp[i][j]\)
\(fail\)是固定的，你又知道\(dp[0]\)的第一行第一列是1，然后求一个\(dp[n]\)就行了... 矩阵快速幂即可....
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define maxn 100010
using namespace std;
int n,m,K;
struct node
{
int a[50][50];
node ()
{
memset(a,0,sizeof(a));
}
};
int nx[50],fail[50][50];
void kmp(char* s)
{
nx[1]=0;
for(int i=2,j=0;i<=m;i++)
{
while(j&&s[j+1]!=s[i]) j=nx[j];
if(s[i]==s[j+1]) j++;
nx[i]=j;
}
for(int i=0;i<m;i++)
{
for(int j='0';j<='9';++j)
{
int tmp=i;
while(tmp&&s[tmp+1]!=j) tmp=nx[tmp];
if(s[tmp+1]==j) tmp++;
if(tmp<m) fail[i][tmp]++;
}
}
}
node mul(node a,node b)
{
node c;
for(int i=0;i<50;i++)
for(int j=0;j<50;j++)
for(int k=0;k<50;k++)
{
c.a[i][j]=(c.a[i][j]+a.a[i][k] * b.a[k][j]%K)%K;
}
return c;
}
node ksm(node a,int b)
{
node ans;
for(int i=0;i<=m;i++) ans.a[i][i]=1;
for(;b;b>>=1)
{
if(b&1) ans=mul(ans,a);
a=mul(a,a);
}
/* for(int i=0;i<=m;i++)
{
for(int j=0;j<=m;j++) cout<<ans.a[i][j]<<" ";
cout<<endl;
}*/
return ans;
}
char s[50];
signed main()
{
scanf("%lld%lld%lld",&n,&m,&K);
cin>>s+1;
kmp(s);
node Ans,qwq,Qwq;
Ans.a[0][0]=1;
/* for(int i=0;i<=m;i++)
{
for(int j=0;j<=m;j++) cout<<fail[i][j]<<" ";
cout<<endl;
}*/
for(int i=0;i<m;i++)
for(int j=0;j<m;j++) qwq.a[i][j]=fail[i][j];
/* for(int i=0;i<=m;i++)
{
for(int j=0;j<=m;j++) cout<<qwq.a[i][j]<<" ";
cout<<endl;
}*/
Qwq=ksm(qwq,n);
/* for(int i=0;i<=m;i++)
{
for(int j=0;j<=m;j++) cout<<Qwq.a[i][j]<<" ";
cout<<endl;
}*/
Ans=mul(Ans,Qwq);
/* for(int i=0;i<=m;i++)
{
for(int j=0;j<=m;j++) cout<<Ans.a[i][j]<<" ";
cout<<endl;
}*/
int ans=0;
for(int i=0;i<m;i++) ans=(ans+Ans.a[0][i])%K;
printf("%lld\n",ans);
return 0;
}