当前位置:网站首页>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题其实可联想最长递增子序列。
边栏推荐
- Gavin teacher's perception of transformer live class - rasa project actual combat e-commerce retail customer service intelligent business dialogue robot system behavior analysis and project summary (4
- Qt QPushButton详解
- C # input how many cards are there in each of the four colors.
- Mysql - CRUD
- Effet Doppler (déplacement de fréquence Doppler)
- 7.5 simulation summary
- Convert Chinese into pinyin
- FFmpeg学习——核心模块
- N1 # if you work on a metauniverse product [metauniverse · interdisciplinary] Season 2 S2
- JS 这次真的可以禁止常量修改了!
猜你喜欢
China Jinmao online electronic signature, accelerating the digitization of real estate business
剖面测量之提取剖面数据
云呐|固定资产管理系统主要操作流程有哪些
Hudi of data Lake (2): Hudi compilation
MySql——CRUD
How much do you know about the bank deposit business that software test engineers must know?
My colleagues quietly told me that flying Book notification can still play like this
[noi simulation] Anaid's tree (Mobius inversion, exponential generating function, Ehrlich sieve, virtual tree)
wx. Getlocation (object object) application method, latest version
Mysql - CRUD
随机推荐
Ffmpeg learning - core module
7.5 装饰器
18.(arcgis api for js篇)arcgis api for js点采集(SketchViewModel)
Effet Doppler (déplacement de fréquence Doppler)
选择致敬持续奋斗背后的精神——对话威尔价值观【第四期】
Global and Chinese market of digital serial inverter 2022-2028: Research Report on technology, participants, trends, market size and share
Yunna | what are the main operating processes of the fixed assets management system
Asynchronous task Whenall timeout - Async task WhenAll with timeout
Key structure of ffmpeg - avformatcontext
PV static creation and dynamic creation
MySql——CRUD
15 MySQL stored procedures and functions
MySQL functions
Upgrade openssl-1.1.1p for openssl-1.0.2k
[SQL] SQL expansion languages of mainstream databases (T-SQL, pl/sql, pl/pgsql)
How to rotate the synchronized / refreshed icon (EL icon refresh)
FFMPEG关键结构体——AVCodecContext
How much do you know about the bank deposit business that software test engineers must know?
[designmode] composite mode
【DesignMode】组合模式(composite mode)