许久未打的CF比赛，水平不行被自己打成了一场手速赛，20分钟过了A和B之后gg，结果赛后把CDE都能补完了
这种训练难度其实是最好的，感觉自己会的，不一定能1A，不一定能写出来，祝自己省赛顺利
A题：数学题，一个n个数字的全排列，所有数字可以任意交换，但是只能交换一次，求最大值n和最小值1的最大的可能距离
要么放到第一个位置，要么放到最后一个位置，枚举即可
int n;
int num[maxn];
int main(){
//input;
while(scanf("%d",&n)!=EOF){
int ans=0;
for(int i=1;i<=n;i++){
scanf("%d",&num[i]);
if (num[i]==n||num[i]==1){
ans=max(ans,n-i);
ans=max(ans,i-1);
}
}
cout<<ans<<endl;
}
return 0;
}
B题：当作模拟题做吧，有dp思想在里面
题意：第n层有n个杯子，每个杯子的容量为1，第i层的第j个杯子一旦满了之后，会把多余的水分给第i+1层的下面两个杯子，问注T个水量，最终有多少个杯子是满的
定义dp【i】【j】
其中dp【1】【1】=T
那么可以一层一层的模拟
首先假设第i层的杯子容量无穷大，那么可以接收第i-1层的所有水（先存着）
等第i-1层的所有水流完，那么第i层的杯子容量变为1，开始把多余的水平均分给第i+1层的下面两个杯子
由于涉及double，记得eps
代码：
double dp[20][20];
int n,t;
int main(){
//input;
while(scanf("%d%d",&n,&t)!=EOF){
memset(dp,0,sizeof(dp));
dp[1][1]=t;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
if (dp[i][j]>=1+eps){
dp[i+1][j]+=(dp[i][j]-1)/2.0;
dp[i+1][j+1]+=(dp[i][j]-1)/2.0;
dp[i][j]=1;
}
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
if (dp[i][j]<1+eps&&dp[i][j]>1-eps)
ans++;
cout<<ans<<endl;
}
return 0;
}
C题是被教做人的一题，二分思路其实很简单
题意：n个长度的字符串，全是a或者b，最多允许修改k个，求可能出现的最大连续相同字符串的长度
思路：最多为n个，最少为0个是显然的，那么二分的左右界限有了
如果检查长度为x的，是不是可能存在
来个O（n）的扫描就好，首先从串起始开始，取x个字符统计a和b的字符数量
然后区间右移动一个，如果x+1（添加）的地方是a，就加1，如果删除的地方是a，就减1
这样每次判断当前字符数量与需要检查的x的差值，不超过k就可以
代码如下：
int n,k;
char s[maxn];
bool ok(int x){
int need=k+1,a=0,b=0;
for(int i=1;i<=x;i++)
if (s[i]=='a') a++;
b=x-a;
need=min(need,x-a);
need=min(need,x-b);
for(int i=x+1;i<=n;i++){
if (s[i]=='a') a++;
else b++;
if (s[i-x]=='a') a--;
else b--;
need=min(need,x-a);
need=min(need,x-b);
}
if (need<=k) return true;
return false;
}
int main(){
//input;
while(scanf("%d%d",&n,&k)!=EOF){
scanf("%s",s+1);
int L=0,R=n,m,ans;
while(L<=R){
m=(L+R)>>1;
if (ok(m)){
ans=m;
L=m+1;
}
else
R=m-1;
}
cout<<ans<<endl;
}
return 0;
}PS：附个二分的学习链接
D题：比赛的时候因为不会搞C，所以觉得D能做
题意：给一个n*m的矩阵，里面的字符表示的是可以往哪几个方向走，或者浪费1秒钟，使用功力让所有的符号顺时针旋转90度，即为把门的朝向改了
这个题的难点：字符怎么跟联通简单的匹配出来；怎么旋转；怎么定义状态
其实想到了很简单：求最小值，用bfs，最多旋转4次，定义step【i】【j】【4】，step【】【】【】=-1代表不可达
顺时针修改字符，就直接暴力用if语句提前预处理了
剩下的难点：用字符表示匹配
我的想法是：用接口对接
意思是：如果当前从（x，y）运动到（nx，ny），方向为K，这儿的K表示枚举的上下左右，以上为例
那么（x，y）需要开放从下到上的接口，意思是搞个flag标记
（nx，ny）需要开放从上到下的接口，意思是搞个flag标记
两个标记同时存在，就可以走
所以判断很简单，四个if语句分开四种方向，每个方向里面两个if语句，判断两边对应的接口是不是存在
bfs还有个很经典的坑点，如果起点和终点是同一个点，那么答案是0
int n,m,sx,sy,ex,ey;
char mp[maxn][maxn][4];
int step[maxn][maxn][4];
char s[maxn][maxn];
int dx[]={0,0,0,1,-1};
int dy[]={0,1,-1,0,0};
struct node{
int x,y,t;
};
bool ok(char c1,char c2,int k){
int flag1=0,flag2=0;
char ch;
if (k==1){//向右走
if (c1=='+'||c1=='-'||c1=='>'||c1=='L'||c1=='U'||c1=='D') flag1=1;
if (c2=='+'||c2=='-'||c2=='<'||c2=='R'||c2=='U'||c2=='D') flag2=1;
}
else if (k==2){//向左走
if (c1=='+'||c1=='-'||c1=='<'||c1=='R'||c1=='U'||c1=='D') flag1=1;
if (c2=='+'||c2=='-'||c2=='>'||c2=='L'||c2=='U'||c2=='D') flag2=1;
}
else if (k==3){//向下走
if (c1=='+'||c1=='|'||c1=='v'||c1=='L'||c1=='R'||c1=='U') flag1=1;
if (c2=='+'||c2=='|'||c2=='^'||c2=='L'||c2=='R'||c2=='D') flag2=1;
}
else if (k==4){//向上走
if (c1=='+'||c1=='|'||c1=='^'||c1=='L'||c1=='R'||c1=='D') flag1=1;
if (c2=='+'||c2=='|'||c2=='v'||c2=='L'||c2=='R'||c2=='U') flag2=1;
}
return flag1&&flag2;
}
void DebugMap(){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
printf("%c%c",mp[i][j][0],j==m?'\n':' ');
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
printf("%c%c",mp[i][j][1],j==m?'\n':' ');
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
printf("%c%c",mp[i][j][2],j==m?'\n':' ');
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
printf("%c%c",mp[i][j][3],j==m?'\n':' ');
}
void DebugStep(){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
printf("%d%c",step[i][j][0],j==m?'\n':' ');
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
printf("%d%c",step[i][j][1],j==m?'\n':' ');
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
printf("%d%c",step[i][j][2],j==m?'\n':' ');
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
printf("%d%c",step[i][j][3],j==m?'\n':' ');
}
void GetMap(){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
mp[i][j][0]=s[i][j];
for(int k=1;k<=3;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if (mp[i][j][k-1]=='-') mp[i][j][k]='|';
else if (mp[i][j][k-1]=='|') mp[i][j][k]='-';
else if (mp[i][j][k-1]=='<') mp[i][j][k]='^';
else if (mp[i][j][k-1]=='v') mp[i][j][k]='<';
else if (mp[i][j][k-1]=='>') mp[i][j][k]='v';
else if (mp[i][j][k-1]=='^') mp[i][j][k]='>';
else if (mp[i][j][k-1]=='D') mp[i][j][k]='L';
else if (mp[i][j][k-1]=='R') mp[i][j][k]='D';
else if (mp[i][j][k-1]=='U') mp[i][j][k]='R';
else if (mp[i][j][k-1]=='L') mp[i][j][k]='U';
else mp[i][j][k]=mp[i][j][k-1];
}
return;
}
int bfs(){
queue<node> q;
while(!q.empty()) q.pop();
node u,v;
u.x=sx;u.y=sy;u.t=0;
q.push(u);
step[u.x][u.y][0]=0;
while(!q.empty()){
u=q.front();q.pop();
if (step[u.x][u.y][(u.t+1)%4]==-1){
v.x=u.x;v.y=u.y;v.t=(u.t+1)%4;
step[v.x][v.y][v.t]=step[u.x][u.y][u.t]+1;
q.push(v);
}
for(int k=1;k<=4;k++){
v.x=u.x+dx[k];
v.y=u.y+dy[k];
if (v.x>=1&&v.x<=n&&v.y>=1&&v.y<=m&&step[v.x][v.y][u.t]==-1&&ok(mp[u.x][u.y][u.t],mp[v.x][v.y][u.t],k)){
if (v.x==ex&&v.y==ey) return step[u.x][u.y][u.t]+1;
step[v.x][v.y][u.t]=step[u.x][u.y][u.t]+1;
v.t=u.t;
q.push(v);
}
}
}
return -1;
}
int main(){
//input;
while(scanf("%d%d",&n,&m)!=EOF){
memset(step,-1,sizeof(step));
for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
if (sx==ex&&sy==ey) cout<<"0"<<endl;
else{
GetMap();
//DebugMap();
//DebugStep();
cout<<bfs()<<endl;
}
}
return 0;
}E题：放在最后一题有点不合理，一个数学思路题
比赛的时候都没看题，好多人说很简单
题意：一个最高项n次的多项式，给（a0，a1，……，an）作为系数，问F(X)是不是可以为0
系数有的是给定的，“？”的情况呢，就是两个人轮流填写任意数值，一人一次，博弈
搞法很简单：正常情况，最后一次填数的人赢！为啥，因为可以随便写什么数字啊！缺什么补什么，不就够了
特殊情况1：X=0，意思是F（X）=0，等价于，a0等于0，也就是常数项等于0
常数项谁能够选择到？判断有多少个？就好
特殊情况2：所有数值都给定了，就直接计算值就好了，判断是不是等于0，相当于写了个数学上的多项式模拟
需要用mod素数的方法把值减小，不然太大了担心爆炸
代码如下：
__int64 mod1=1e9+7,mod2=3e8+7,mod3=1e8+9,mod4=5e8+1;
__int64 n,x,a[100009],cnt,i;
char s[100020][20];
int main(){
//input;
while(scanf("%I64d%I64d",&n,&x)!=EOF){
cnt=0;
for(i=0;i<=n;i++){
scanf("%s",s[i]);
if (s[i][0]=='?') cnt++;
}
if (x==0){
if (s[0][0]=='?'){
if ((n+1-cnt)%2==1) puts("Yes");
else puts("No");
}
else{
if (s[0][0]=='0') puts("Yes");
else puts("No");
}
}
else{
if (cnt==0){
for(i=0;i<=n;i++){
a[i]=0;
bool minus=(s[i][0]=='-');
__int64 j=minus;
__int64 len=strlen(s[i]);
while(j<len) a[i]=a[i]*10+s[i][j++]-'0';
if (minus) a[i]=-a[i];
}
__int64 w1=1,w2=1,w3=1,w4=1,s1=0,s2=0,s3=0,s4=0;
for(i=0;i<=n;i++){
s1=(s1+w1*a[i])%mod1;
s2=(s2+w2*a[i])%mod2;
s3=(s3+w3*a[i])%mod3;
s4=(s4+w4*a[i])%mod4;
w1=w1*x%mod1;
w2=w2*x%mod2;
w3=w3*x%mod3;
w4=w4*x%mod4;
}
if (s1==0 && s2==0 && s3==0 && s4==0) printf("Yes\n");
else printf("No\n");
}
else printf("%s\n",(n%2==1)?"Yes":"No");
}
}
return 0;
}
京公网安备 11010502036488号