当前位置:网站首页>Codeforces Round #804 (Div. 2)【比赛记录】
Codeforces Round #804 (Div. 2)【比赛记录】
2022-07-06 00:06:00 【瘾ิۣۖิۣۖิۣۖิꦿ】
A — The Third Three Number Problem
A题很容易即可发现,n为奇数时无解,n为偶数时,n/2,n/2,0即可。
#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
const int Max=2e5+5;
const int Mod=998244353;
int main(){
int t,n;sc(t);
while(t--){
sc(n);
if(n%2==0){
printf("%d %d 0\n",n/2,n/2);
}else{
printf("-1\n");
}
}
}
B — Almost Ternary Matrix
构造题,很容易即可发现
1 0 0 1 ...
0 1 1 0 ...
0 1 1 0 ...
1 0 0 1 ...
1 0 0 1 ...
...
以这种形式构造即可。
#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
const int Max=2e5+5;
const int Mod=998244353;
int dp[100][100];
int main(){
int t,n;sc(t);
while(t--){
int m;sc(n);sc(m);
int x=1;
int num=x;
for(int j=1;j<=m;j+=2){
dp[1][j]=num;
dp[1][j+1]=num^1;
num^=1;
}
for(int i=2;i<n;i+=2){
num=x^1;x=x^1;
int temp=num;
for(int k=i;k<=i+1;k++){
num=temp;
for(int j=1;j<=m;j+=2){
dp[k][j]=num;
dp[k][j+1]=num^1;
num^=1;
}
}
}
num=x^1;
for(int j=1;j<=m;j+=2){
dp[n][j]=num;
dp[n][j+1]=num^1;
num^=1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
printf("%d ",dp[i][j]);
}
printf("\n");
}
}
}
C — The Third Problem
C题是最可惜的一题。下面讲讲我比赛时的错误思路:0和1的位置是不可变的,0和1位置中间的2,3,4,5...x(x是0和1位置中间不存在的顺序数字)个数,这几个数字一定在0和1位置之间放置,然后找0和1位置之外的x,x+1,x+2...y(y是0和1位置中间之外不存在的顺序数字),这几个数字一定不可动,剩余数字全排列。(可惜差一点点就是正解了,太菜了T-T)
正确思路:很容易会发现,0和1的位置是不可变的,此时的区间假设是【l,r】,如果数字2出现在此区间,则2一定在此区间移动,不可出此区间,则2可能的位置种数就是r-l-1(数字为i时,种数为r-l+1-i);如果2出现在此区间之外,那么2一定不可动,区间扩充为【l,pos[2]】或者【pos[2],r】,以此类推。
#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
const int Max=2e5+5;
const int mod=1e9+7;
int a[Max];
int pos[Max];
int main(){
int t,n;sc(t);
while(t--){
sc(n);
for(int i=1;i<=n;i++){
sc(a[i]);pos[a[i]]=i;
}
int l=pos[0],r=pos[0];
ll ans=1;
for(int i=1;i<n;i++){
if(pos[i]<l) l=pos[i];
else if(pos[i]>r) r=pos[i];
else ans*=(r-l+1-i),ans%=mod;
}
printf("%lld\n",ans);
}
}
D — Almost Triple Deletions
定理:数组a1,a2,a3...an可全部删除的条件:
1.n为偶数。
2.数组中任何元素出现的最大频率最多为n/2。
定义:令 dp[i]为由 ai 和前 i−1 个元素的某个子数组组成的最终数组的最大长度。最初,如果前缀 [a1,a2,…,ai−1] 可以完全删除,则 dp[i]设置为 1。否则,dp[i]=0。
如果位置a[i]==a[j],i和j想合并,那么 [aj+1,aj+2,…,ai−1] 必须可删除,如此得到递推公式
dp[i]=max(dp[i],dp[j]+1),j为i+1~n+1
注意:如果我们将最终数组定义为来自数组 a 的相等元素的子数组,an+1 被强制附加到该子数组,那么最终答案可以写为 dp[n+1]− 1.请注意,在计算 dp[n+1] 时,不应将 aj 与 an+1 进行比较。
#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
const int Max=2e5+5;
const int mod=1e9+7;
int a[Max];
int dp[Max];
int sum[Max],n;
int main(){
int t;sc(t);
while(t--){
sc(n);
for(int i=1;i<=n;i++) sum[i]=0;
for(int i=1;i<=n;i++) sc(a[i]);
int maxa=0;
for(int i=1;i<=n+1;i++){
if(i==1) dp[i]=1;
else if(i%2==0) dp[i]=0;
else if(maxa>(i-1)/2) dp[i]=0;
else dp[i]=1;
sum[a[i]]++;
maxa=max(maxa,sum[a[i]]);
}
for(int i=1;i<=n;i++){
if(dp[i]==0) continue;
maxa=0;
for(int i=1;i<=n;i++) sum[i]=0;
for(int j=i+1;j<=n+1;j++){
if((a[i]==a[j]||j==n+1)&&(j-i-1)%2==0&&maxa<=(j-i-1)/2){
dp[j]=max(dp[j],dp[i]+1);
}
sum[a[j]]++;
maxa=max(sum[a[j]],maxa);
}
}
printf("%d\n",dp[n+1]-1);
}
}
/*
1
3
3 3 1
*/
总结:比赛时一直以为代码出了毛病,没想到思路错了,罚坐一个半小时,以后比赛时,碰见这类题,及时跳,最主要的还是重新验证思路是否有误。D题其实可联想最长递增子序列。
边栏推荐
- There is no network after configuring the agent by capturing packets with Fiddler mobile phones
- wx. Getlocation (object object) application method, latest version
- 【NOI模拟赛】Anaid 的树(莫比乌斯反演,指数型生成函数,埃氏筛,虚树)
- Mysql - CRUD
- Zero rhino technology joined hands with the intelligence Club: the "causal faction" forum was successfully held, and the "causal revolution" brought the next generation of trusted AI
- 14 MySQL view
- Initialiser votre vecteur & initialisateur avec une liste Introduction à la Liste
- 【二叉搜索树】增删改查功能代码实现
- 7.5模拟赛总结
- 云呐|固定资产管理系统主要操作流程有哪些
猜你喜欢
用列表初始化你的vector&&initializer_list简介
Qt QPushButton详解
FFmpeg学习——核心模块
FFMPEG关键结构体——AVFormatContext
Laser slam learning record
Yunna | what are the main operating processes of the fixed assets management system
[binary search tree] add, delete, modify and query function code implementation
云呐|固定资产管理系统功能包括哪些?
云呐|固定资产管理系统主要操作流程有哪些
提升工作效率工具:SQL批量生成工具思想
随机推荐
数据库遇到的问题
The use of El cascader and the solution of error reporting
Mysql - CRUD
从底层结构开始学习FPGA----FIFO IP核及其关键参数介绍
My colleagues quietly told me that flying Book notification can still play like this
"14th five year plan": emphasis on the promotion of electronic contracts, electronic signatures and other applications
Initialize your vector & initializer with a list_ List introduction
Global and Chinese market of digital serial inverter 2022-2028: Research Report on technology, participants, trends, market size and share
Problems encountered in the database
Problem solving win10 quickly open ipynb file
How to rotate the synchronized / refreshed icon (EL icon refresh)
教你在HbuilderX上使用模拟器运行uni-app,良心教学!!!
[SQL] SQL expansion languages of mainstream databases (T-SQL, pl/sql, pl/pgsql)
Senparc.Weixin.Sample.MP源码剖析
激光slam学习记录
跟着CTF-wiki学pwn——ret2libc1
什么叫做信息安全?包含哪些内容?与网络安全有什么区别?
FFMPEG关键结构体——AVCodecContext
时区的区别及go语言的time库
Huawei equipment configuration ospf-bgp linkage