当前位置:网站首页>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题其实可联想最长递增子序列。
边栏推荐
- DEJA_VU3D - Cesium功能集 之 055-国内外各厂商地图服务地址汇总说明
- The use of El cascader and the solution of error reporting
- [gym 102832h] [template] combination lock (bipartite game)
- CloudCompare&PCL 点云随机添加噪声
- Qt 一个简单的word文档编辑器
- Knowledge about the memory size occupied by the structure
- C reflection and type
- The difference of time zone and the time library of go language
- [designmode] composite mode
- 关于结构体所占内存大小知识
猜你喜欢
Learn PWN from CTF wiki - ret2libc1
JVM details
MySQL之函数
微信小程序---WXML 模板语法(附带笔记文档)
用列表初始化你的vector&&initializer_list简介
Single merchant v4.4 has the same original intention and strength!
The difference of time zone and the time library of go language
【二叉搜索树】增删改查功能代码实现
[designmode] composite mode
FFT 学习笔记(自认为详细)
随机推荐
FFT learning notes (I think it is detailed)
Which side projects can be achieved? Is it difficult for we media to earn more than 10000 a month?
Use CAS instead of synchronized
Mathematical model Lotka Volterra
7.5模拟赛总结
Global and Chinese market of digital serial inverter 2022-2028: Research Report on technology, participants, trends, market size and share
Recognize the small experiment of extracting and displaying Mel spectrum (observe the difference between different y_axis and x_axis)
Asynchronous task Whenall timeout - Async task WhenAll with timeout
FFMPEG关键结构体——AVFormatContext
JVM details
什么叫做信息安全?包含哪些内容?与网络安全有什么区别?
What are Yunna's fixed asset management systems?
总结了 800多个 Kubectl 别名,再也不怕记不住命令了!
【在线聊天】原来微信小程序也能回复Facebook主页消息!
Open3D 点云随机添加噪声
How much do you know about the bank deposit business that software test engineers must know?
Yunna | what are the main operating processes of the fixed assets management system
Tools to improve work efficiency: the idea of SQL batch generation tools
零犀科技携手集智俱乐部:“因果派”论坛成功举办,“因果革命”带来下一代可信AI
亲测可用fiddler手机抓包配置代理后没有网络