当前位置:网站首页>Codeforces round 804 (Div. 2) [competition record]
Codeforces round 804 (Div. 2) [competition record]
2022-07-06 00:12:00 【Addiction ۣۖ ิ ۣۖ ิ ۣۖ ิꦿ】
A — The Third Three Number Problem
A The question is easy to find ,n There is no solution when it is an odd number ,n For even when ,n/2,n/2,0 that will do .
#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
Construction question , It's easy to find
1 0 0 1 ...
0 1 1 0 ...
0 1 1 0 ...
1 0 0 1 ...
1 0 0 1 ...
...
It can be constructed in this form .
#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 Question is the most regrettable one . Now let's talk about my game Wrong thinking :0 and 1 The position of is immutable ,0 and 1 In the middle of the position 2,3,4,5...x(x yes 0 and 1 Sequence number that does not exist in the middle of the position ) Number , These figures must be 0 and 1 Place between positions , And find 0 and 1 Out of position x,x+1,x+2...y(y yes 0 and 1 Sequence numbers that do not exist outside the middle of the position ), These figures must not be moved , The remaining numbers are all arranged .( Unfortunately, it's almost the positive solution , It's so delicious T-T)
The right way of thinking : It's easy to find ,0 and 1 The position of is immutable , The interval assumption at this time is 【l,r】, If the number 2 Appear in this interval , be 2 Must move in this range , Do not leave this interval , be 2 The number of possible positions is r-l-1( The number is i when , The number of species is r-l+1-i); If 2 Appear outside this interval , that 2 It must not move , The interval is expanded to 【l,pos[2]】 perhaps 【pos[2],r】, And so on .
#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
Theorem : Array a1,a2,a3...an Conditions that can be deleted completely :
1.n For the even .
2. The maximum frequency of any element in the array is n/2.
Definition : Make dp[i] citing ai And the former i−1 The maximum length of the final array composed of a sub array of elements . first , If the prefix [a1,a2,…,ai−1] It can be deleted completely , be dp[i] Set to 1. otherwise ,dp[i]=0.
If the position a[i]==a[j],i and j Want to merge , that [aj+1,aj+2,…,ai−1] Must be removable , So we get the recurrence formula
dp[i]=max(dp[i],dp[j]+1),j by i+1~n+1
Be careful : If we define the final array as coming from the array a Subarray of equal elements of ,an+1 Is forcibly attached to the subarray , Then the final answer can be written as dp[n+1]− 1. Please note that , In the calculation dp[n+1] when , Should not aj And an+1 Compare .
#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
*/
summary : I always thought there was something wrong with the code during the game , I didn't expect that I was wrong , Sit for an hour and a half , In future competitions , Encounter this kind of problem , Jump in time , The most important thing is to re verify whether the idea is wrong .D In fact, the question can be associated with the longest increasing subsequence .
边栏推荐
- Problem solving win10 quickly open ipynb file
- Redis high availability - master-slave replication, sentinel mode, cluster
- Problems encountered in the database
- CloudCompare&PCL 点云随机添加噪声
- The global and Chinese markets of dial indicator calipers 2022-2028: Research Report on technology, participants, trends, market size and share
- How to get all the values stored in localstorage
- 【DesignMode】组合模式(composite mode)
- FFT learning notes (I think it is detailed)
- Learn PWN from CTF wiki - ret2libc1
- Configuring OSPF GR features for Huawei devices
猜你喜欢
传输层协议------UDP协议
Open source CRM customer relationship system management system source code, free sharing
数据库遇到的问题
【DesignMode】组合模式(composite mode)
Wechat applet -- wxml template syntax (with notes)
"14th five year plan": emphasis on the promotion of electronic contracts, electronic signatures and other applications
微信小程序---WXML 模板语法(附带笔记文档)
How to rotate the synchronized / refreshed icon (EL icon refresh)
Hardware and interface learning summary
Initialize your vector & initializer with a list_ List introduction
随机推荐
mysql-全局锁和表锁
Configuring OSPF GR features for Huawei devices
总结了 800多个 Kubectl 别名,再也不怕记不住命令了!
选择致敬持续奋斗背后的精神——对话威尔价值观【第四期】
7.5模拟赛总结
[designmode] composite mode
Permission problem: source bash_ profile permission denied
[online chat] the original wechat applet can also reply to Facebook homepage messages!
There is no network after configuring the agent by capturing packets with Fiddler mobile phones
【luogu CF487E】Tourists(圆方树)(树链剖分)(线段树)
FFMPEG关键结构体——AVFormatContext
【在线聊天】原来微信小程序也能回复Facebook主页消息!
About the slmgr command
Zhuan: in the future, such an organization can withstand the risks
多普勒效應(多普勒頻移)
[binary search tree] add, delete, modify and query function code implementation
USB Interface USB protocol
MySQL functions
Zhongjun group launched electronic contracts to accelerate the digital development of real estate enterprises
Cloudcompare & PCL point cloud randomly adds noise