当前位置:网站首页>Codeforces Round #804 (Div. 2)(A~D)
Codeforces Round #804 (Div. 2)(A~D)
2022-07-07 22:48:00 【_dawn°】
A. The Third Three Number Problem
给出一个数n,找到三个数a,b,c,使得这三个数相互异或得到三个数的和等于n。
思路:其实我的思路是看到第一个样例解释来的,,
然后就想到可以是两个数相同,这样三个数的和就可以转化为两个数的和,而对于偶数,直接用n/2和0异或即可;对于奇数,样例中的1不满足,然后我就直接猜测奇数不可以满足条件,事实证明这个是可以证明的:假设二进制最后一位有k个1和3-k个0,那n的二进制最后一位的奇偶性与k*(3-k)相同,那么n的二进制最后一位应该恒为0。
AC Code:
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
typedef long long ll;
const int mod=1e9+7;
const int N=55;
int t,n;
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin>>t;
while(t--){
std::cin>>n;
if(n&1){
std::cout<<-1<<'\n';
continue;
}
std::cout<<n/2<<' '<<n/2<<' '<<0<<'\n';
}
return 0;
}
B. Almost Ternary Matrix
给出两个偶数,构造一个01矩阵,使得每个方块周围与它不同的方块数是2。
思路:自己画一下试试,会发现我们可以找到一个4*4的单元矩阵,根据这个单位矩阵循环输出即可,单位矩阵如下:
当然,01可以互换,这样代码就很简单了。
AC Code:
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
typedef long long ll;
const int mod=1e9+7;
const int N=55;
int t,n,m;
int ans[4][4]={1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1};
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin>>t;
while(t--){
std::cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
std::cout<<ans[i%4][j%4]<<" \n"[j==m-1];
}
}
}
return 0;
}
os:一开始因为怎么写代码想了半天hhhhh
C. The Third Problem
给出一个permutation,不过是从0~n-1,问有多少种重新排列这些数的方法,使得重新排序后的数组对于每个区间的MEX值相等。
思路:看到这个题,大概就是一个排列组合类似的题。根据观察我们可以发现,对于每一个数,只要这个数向前向后都有比该数小的元素存在,那这个数就可以在这个范围内移动,比如样例4:
1 3 7 2 5 0 6 4
比2小的只有0和1,那2就可以在第2到第五个位置移动;3也只能在这个范围内移动,因为比3小的数最向外只能到0和1的位置;而对于在比自己小的数字外围的数字,他们的位置是不能动的,比如4,比它小的0,1,2,3都在前面,很容易理解它的位置如果变化,那一定存在区间的MEX值变化了。根据这个性质,我们可以根据数字大小排序,从小到大枚举,不断更新比当前数小的数的最大范围区间,计算每个数有几种选择位置的方法,相乘即可。当然,0和1作为初始的区间范围,0和1的位置一定不能动。
AC Code:
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
typedef long long ll;
const int mod=1e9+7;
const int N=1e5+5;
int t,n;
int a[N];
struct node{
int id,num;
bool operator<(const node &a) const{
return num<a.num;
}
} e[N];
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin>>t;
while(t--){
std::cin>>n;
for(int i=1;i<=n;i++){
std::cin>>a[i];
e[i].id=i;
e[i].num=a[i];
}
std::sort(e+1,e+1+n);
int r=-1,l=1e9;
ll ans=1;
for(int i=1;i<=n;i++){
r=std::max(r,e[i].id);
l=std::min(l,e[i].id);
if(i>2&&e[i].id>l&&e[i].id<r){
ans*=(r-l-1-i+3);
ans%=mod;
}
}
std::cout<<ans<<'\n';
}
return 0;
}
os:二十多分钟搞定前两个题,后面一直在想C,最后五分钟交的hhhh
D. Almost Triple Deletions
给出一个数组,若相邻两个数不同,那可以删去这两个数。最终操作完成后数组中剩余的数都相等,问最多可以保留几个数。
思路:学习大佬的思路,太顶了
我们可以认为操作的最后结果是删除部分连续区间,而对于一个区间[l,r]来说,当且仅当满足下列条件时,可以删除:区间长是偶数;区间中出现最频繁的元素的个数最大为(r-l+1)/2。
必要性一定,证明充分性:
对于出现最频繁的数,一定可以找到一种方法,删去一个和另外一个数,那么还剩下的出现次数t<=(r-l+1)/2-1;如果删除后,这个数还是出现次数最多的,那它还是满足初始条件,依旧可以删除一个该数和另一个数;如果删除后它不是出现次数最多的数了,那一定有另外一个数满足出现次数最多的初始条件,可以删除一个该数和另外一个数,这样就是这个区间内元素之间的相互转化,最后到达平衡时就是两个元素出现次数相等,都等于l/2,这样一定是可以删去的,使得该区间长为0,证毕。
所以我们可以先处理区间可以删除的子区间,cel[l][r]=1,我们定义DP数组f[i]表示从第一个到第i个数,删去部分数达到所有数都等于a[i]后,剩余的个数最大值,f[i]到f[j]的转化方程可以表示为删除区间[j,i],使得f[i]=f[j]+1。
最后的答案不一定是f[n],因为最后剩下的数不一定都等于a[n],所以需要扫一遍取最大值。
数据范围n<=5000,O(n^2)能过。
AC Code:
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
typedef long long ll;
const int mod=1e9+7;
const int N=5e3+5;
int t,n;
int a[N];
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin>>t;
while(t--){
std::cin>>n;
for(int i=1;i<=n;i++){
std::cin>>a[i];
}
int cel[n+1][n+1]={0};
for(int l=1;l<=n;l++){
int cnt[n+1]={0},max=0;
for(int r=l;r<=n;r++){
cnt[a[r]]++;
max=std::max(max,cnt[a[r]]);
if((r-l+1)%2==0&&max*2<=r-l+1)
cel[l][r]=1;
}
}
int f[n+1]={0};
int ans=0;
for(int i=1;i<n;i++){
if(cel[1][i])
f[i+1]=1;
}
f[1]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
if((j+1>i-1||cel[j+1][i-1]==1)&&a[j]==a[i]&&f[j]>0)
f[i]=std::max(f[i],f[j]+1);
}
if(i==n||cel[i+1][n]) ans=std::max(ans,f[i]);
}
std::cout<<ans<<'\n';
}
return 0;
}
os:怪,这个题卡memset
嘿嘿嘿,青啦青啦!
若有错误请指教,谢谢!
边栏推荐
- 【obs】官方是配置USE_GPU_PRIORITY 效果为TRUE的
- RPA cloud computer, let RPA out of the box with unlimited computing power?
- 动态库基本原理和使用方法,-fPIC 选项的来龙去脉
- 接口测试要测试什么?
- 去了字节跳动,才知道年薪 40w 的测试工程师有这么多?
- Su embedded training - day4
- 1293_ Implementation analysis of xtask resumeall() interface in FreeRTOS
- Experience of autumn recruitment in 22 years
- The method of server defense against DDoS, Hangzhou advanced anti DDoS IP section 103.219.39 x
- 【愚公系列】2022年7月 Go教学课程 006-自动推导类型和输入输出
猜你喜欢
SQL knowledge summary 004: Postgres terminal command summary
Smart regulation enters the market, where will meituan and other Internet service platforms go
3 years of experience, can't you get 20K for the interview and test post? Such a hole?
redis你到底懂不懂之list
RPA云电脑,让RPA开箱即用算力无限?
Langchao Yunxi distributed database tracing (II) -- source code analysis
1293_FreeRTOS中xTaskResumeAll()接口的实现分析
某马旅游网站开发(对servlet的优化)
Stm32f1 and stm32cubeide programming example - rotary encoder drive
Notice on organizing the second round of the Southwest Division (Sichuan) of the 2021-2022 National Youth electronic information intelligent innovation competition
随机推荐
[the most detailed in history] statistical description of overdue days in credit
QT establish signal slots between different classes and transfer parameters
Coindesk comments on the decentralization process of the wave field: let people see the future of the Internet
Tencent security released the white paper on BOT Management | interpreting BOT attacks and exploring ways to protect
If an exception is thrown in the constructor, the best way is to prevent memory leakage?
他们齐聚 2022 ECUG Con,只为「中国技术力量」
Qt不同类之间建立信号槽,并传递参数
The underlying principles and templates of new and delete
手写一个模拟的ReentrantLock
The difference between -s and -d when downloading packages using NPM
Development of a horse tourism website (realization of login, registration and exit function)
Daily question brushing record (16)
How does the markdown editor of CSDN input mathematical formulas--- Latex syntax summary
Sqlite数据库存储目录结构邻接表的实现2-目录树的构建
去了字节跳动,才知道年薪 40w 的测试工程师有这么多?
Service Mesh的基本模式
After going to ByteDance, I learned that there are so many test engineers with an annual salary of 40W?
深潜Kotlin协程(二十三 完结篇):SharedFlow 和 StateFlow
An error is reported during the process of setting up ADG. Rman-03009 ora-03113
5g NR system messages