首页 > 其他分享 >YL 模拟赛总结 5

YL 模拟赛总结 5

时间:2024-03-02 21:46:33浏览次数:27  
标签:总结 pre YL int res 矩阵 模拟 1031 dp

Problem


T1

\(m\) 个人中间必定有 \(m-1\) 个空位,剩下 \(n-m+1\) 个位置可以随意放人,则方案数为 \(A^{m}_{n-m+1}\)。

T2

考虑进行 \(dp\)。

状态:令 \(dp_{i,j}\) 表示字符串 \(S_{i \sim j}\) 要变成回文串需要添加的最少字符数。

转移:

枚举区间左端点 \(l\) 和长度 \(k\),右端点为 \(r\)。显然需要进行分类讨论:

若 \(S_l=S_r\),则不需要添加字符,于是 \(dp_{l,r}=dp_{l+1,r-1}\);

否则,可以在 \(l\) 前或 \(r\) 之后添加字符,于是 \(dp_{l,r}=\min(dp_{l+1,r},dp_{l,r-1})+1\)。

#include<bits/stdc++.h>
#define int long long
using namespace std;

string s;
int dp[1031][1031];

signed main(){
    cin>>s;
    for(int k=2;k<=s.size();k++){
        for(int l=0;l+k-1<s.size();l++){
            int r=l+k-1;
            if(s[l]==s[r]) dp[l][r]=dp[l+1][r-1];
            else dp[l][r]=min(dp[l+1][r],dp[l][r-1])+1;
        }
    }
    cout<<dp[0][s.size()-1];
    return 0;
}

T3

我们可以先写一个 \(\text{brute-force}\),预处理出 \(1 \sim 9\) 位数的各个数位上的数之和的前缀和数组。

然后对于输入的 \(n\),若其数位为 \(s\),则答案为 \(s\) 位数的最小数到 \(n\) 的各个数位上的数之和 \(+ \ sum_{s-1}\),其中 \(sum\) 是我们刚刚求出来的前缀和数组。

但是这样还是会超时。进一步的,若 \(n\) 更靠近 \(s\) 位数的最小数,则使用上述算法,否则答案为 \(sum_s - s\) 位数的最小数到 \(n\) 的各个数位上的数之和 \(+ \ sum_{s-1}\)。

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;

int n;
int t[31]={0,45,900,13500,180000,2250000,27000000,315000000,3600000000,40500000000,1};

//省略快读

int ws(int x){
	int res=0;
	while(x) res++,x/=10;
	return res;
}
int f(int x){
    int res=0;
    while(x) res+=x%10,x/=10;
    return res;
}
int gz(int x){
	int res=0;
	while(x) res+=pow(10,x-1)*9,x--;
	return res;
}

signed main(){
	//freopen("count.in","r",stdin);
	//freopen("count.out","w",stdout);
	n=read();
	int res=0,s=ws(n),w=gz(s); //cout<<gz(s)<<'\n';
	if(w-n>n-pow(10,s-1)){
		for(int i=pow(10,s-1);i<=n;i++) res+=f(i);
		write(res+t[s-1]);
	}
	else{
		for(int i=w;i>n;i--) res+=f(i);
		write(t[s]-res);
	}
	return 0;
}

T4

还是考虑 \(dp\)。

状态:令 \(dp_{i,j}\) 表示大小为 \(i\) 行 \(j\) 列的矩阵是否能必胜。

转移:

我们首先需要预处理出 \(pre\) 数组,其中 \(pre_{0,i,j}\) 表示大小为 \(i\) 行 \(j\) 列的矩阵是否可以删除最后一列,\(0\) 表示可以,转移方程:

\[pre_{0,i,j}=(pre_{0,i-1,j}+mp_{i,j}) \bmod 2 \]

(\(mp_{i,j}\) 是输入的矩阵)

\(pre_{1,i,j}\) 同理可得。

然后进行 \(dfs\)。

若当前矩阵的最后一列能被删除且删除之后的矩阵未被计算过,则对删去最后一行继续进行 \(dfs\),最后一行同理。

递归返回的时候,若当前矩阵最后一列能被删除,则令 \(a=!dp_{x,y}\)(\(x,y\) 为当前矩阵的规模),最后一行同理,用 \(b\) 记录。

为什么要取反呢?因为递归返回时,若当前矩阵能必胜,则上一层的矩阵是另一个人进行操作,所以不能必胜。必败的情况同理。

最后,将 \(dp_{x,y}\) 设为 \(a \operatorname{or} b\) 即可。

#include<bits/stdc++.h>
using namespace std;

int t,n,mark;
int mp[1031][1031];
int pre[2][1031][1031];
int dp[1031][1031];
bool vis[1031][1031];

void dfs(int x,int y){
    vis[x][y]=mark;
    bool a=0,b=0;
    if(!x||!y){ dp[x][y]=0; return; }
    if(!pre[0][x][y]&&vis[x][y-1]!=mark) dfs(x,y-1);
    if(!pre[1][x][y]&&vis[x-1][y]!=mark) dfs(x-1,y);
    if(!pre[0][x][y]) a=!dp[x][y-1];
    if(!pre[1][x][y]) b=!dp[x-1][y];
    dp[x][y]=(a||b);
}

void solve(){
    cin>>n,mark++;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            cin>>mp[i][j];
            pre[0][i][j]=(pre[0][i-1][j]+mp[i][j])%2;
            pre[1][i][j]=(pre[1][i][j-1]+mp[i][j])%2;
        }
    dfs(n,n);
    cout<<(dp[n][n]?"W\n":"L\n");
}

int main(){
    ios::sync_with_stdio(0);
    cin>>t;
    while(t--) solve();
    return 0;
}

标签:总结,pre,YL,int,res,矩阵,模拟,1031,dp
From: https://www.cnblogs.com/XOF-0-0/p/18049272

相关文章

  • YL 模拟赛总结 4
    ProblemT1遍历字符串,拿一个桶统计即可。T2当\(x\)为中位数时,我们应当尽量的让整个数列的和变小,然后直接在最后一个上加即可。为了让整个数列有序,和最小的构造的数列应当是\(0,0,\cdot\cdot\cdot,x,x,\cdot\cdot\cdot,x\),此时的和应是\(\lfloor\dfrac{n+1}{2}\rflo......
  • YL 模拟赛总结 3
    ProblemT1累加燃烧度,除以\(m\)即为答案。需要开unsigned__int128,差评。T2若有\(a,b\)满足\(a-c=c-b\),化简此式可得\(a+b=2c\),说明\(a+b\)必须为偶数。于是我们倒序求一遍后缀偶数个数\(os_i\)和奇数个数\(js_i\);然后枚举每一个\(i\),若它是奇数,则它可以和它......
  • 2023-2024第一学期的助教工作总结(教务处老师助教)
    一.帮助老师整理开会后的电子版例会总结,整理各类考试试卷以及完成各类文档二.助教工作的每周时长不定,具体安排是整理电子版例会总结和整理考试试卷三.目前我自己的助教工作还处在初阶阶段,主要是帮助老师处理事情,老师平时很忙,平时帮助老师处理一些小事情,也为老师腾出时间来更......
  • 数学之概率题目总结
    前言如有错误,欢迎各位dalao指出。前置芝士:概率T1题目传送门可以看见,标签是入门,一定非常水。显然,要让小D获胜,我们只需要选出\(max(v,w)\rightarrow6\)这一段的任意一个值即可获胜,注意特判一下\(max(v,w)>6\)的情况就行了。还是比较水。T2题目传送门老师抽我起......
  • 0/1分数规划总结
    前言最近在搞什么树套树,博弈论,啥啥啥的,时间实在紧迫,就先拿0/1规划开刀。0/1分数规划是什么实际上是一类问题。顾名思义,0/1即对于\(n\)个物品,选择或者不选择。分数,即对于每个物体,有两个属性\(a_i,b_i\),选出物品的价值就是\(\dfrac{\suma_i\timesd_i}{\sumb_i\tim......
  • 每日总结
    1.在java中,数组是一个对象,不是一种原生类,对象所以存放在堆中,又因为数组特性,是连续的。2.用户不能调用构造方法,只能通过new关键字自动调用。这句话是错误的。在类内部可以用户可以使用关键字this.构造方法名()调用(参数决定调用的是本类对应的构造方法)在子类中用户可以通过......
  • Linux_Centos_yum报错总结
    ​此篇适用于yum报错【尝试其他镜像】并且【curl外网】不通的情况,此时一般考虑是网络的问题一,出现的报错信息: 此时测试curl/pingwww.baidu.com会发现无法连通 二,解决方法:1,首先查看dns的配置文件/etc/resolv.conf检查这里的nameserver这里有时候会因为第二个网卡......
  • YL 模拟赛总结 15
    ProblemT1感觉是最难的。考虑贪心。首先对牛的按左端点进行排序,然后对于每只鸡去考虑匹配哪头牛。具体地,开一个小根堆,然后对于每只鸡\(t_i\),将\(a_i\let_i\)的牛放入堆中,此时堆中存放的是候选的牛。然后对于堆中的牛,将\(b_i<t_i\)的牛弹出。此时堆中的牛均是合法的......
  • YL 模拟赛总结 14
    Problem省流:三道题写了tjT1见tj。T2见tj。T3见tj。T4二分求出左右端点即可。#include<bits/stdc++.h>usingnamespacestd;intn,q;intp[200031];intmain(){//freopen("haybales.in","r",stdin);//freopen("haybales.out",&quo......
  • YL 模拟赛总结 13
    ProblemT1略。T2略。T3考虑对于每一头向北的牛,计算它能够挡住/被挡住几头向东的牛。一头向北的牛\(i\)能够被向东的牛\(j\)挡住的条件是:\(x_i<x_j\)且\(y_i<y_j\)(\(x_i,y_i\)分别表示牛\(i\)的\(x\)坐标与\(y\)坐标);\(l_j\)没有被更新(\(l_i\)表示第......