2024中国计算机学会CSP-S认证提高组第二轮解析
本帖最后由 Randle 于 2024-11-6 20:39 编辑2024的CSP-S刚刚落幕,有申诉需求的同学们抓紧了中国计算机学会官方申诉链接
个人觉得这次主办方出题很有区分度,甚至有出题人可以猜到做题人心思的感觉
本贴是鄙人的代码和思路,有什么问题欢迎各位指出
T1
#include<bits/stdc++.h>
#include<queue>
using namespace std;
const int N = 1e5 + 5;
int a;
queue<int> q;
int main(){
int n;scanf("%d",&n);
for(int i = 0; i <= n-1; i++){
scanf("%d",&a);
}
sort(a,a+n);
for(int i = 0; i <= n-1; i++){
if(q.empty()){
q.push(a);
}else{
if(q.front() < a){
q.pop();
}
q.push(a);
}
}
printf("%d",q.size());
return 0;
}
我一看先贪心算法,因为无后效性就直接贪,用一个队列queue,更清楚
核心代码是判断后入的是否大于队首,若大于则弹出队首,不大于就直接插队尾,最后输出队列长度就是答案
T2
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int csy;
int zjcsy;
struct cifmt{
int dx;
int stv;
int a;
}car;
int main(){
freopen("detect.in","r",stdin);
freopen("detect.out","w",stdout);
memset(zjcsy,0,sizeof(zjcsy));
int t;cin>>t;
int n,m,l,v;
for(int i = 1; i <= t; i++){
cin>>n>>m>>l>>v;
int col = 0;int sum;
int bsum = 0;
for(int j = 1; j <= n; j++){
cin>>car.dx>>car.stv>>car.a;
}
for(int k = 1; k <= m; k++){
cin>>csy;
}
for(int ddq = 1; ddq <= n; ddq++){
if(car.a == 0 && car.stv > v){
col++;
for(int ppq = 1; ppq <= m; ppq++){//注意判断这时候dx是不是刚好是一个csy
if(csy == car.dx){
zjcsy++;
}else if(csy == car.dx ){
zjcsy++;
cout<<zjcsy<<endl;
break;
}else if(csy < car.dx && car.dx < csy){
zjcsy++;
cout<<zjcsy<<endl;
break;
}
}
}else if(car.a > 0){
if(car.stv > v){
if(car.dx <= csy){
col++;
for(int jsx = 1; jsx <= m; jsx++){
if(csy == car.dx){
zjcsy++;
cout<<zjcsy<<endl;
break;
}else if(csy < car.dx && car.dx < csy){
zjcsy++;
cout<<zjcsy<<endl;
break;
}
}
}
}else if(car.stv == v){//注意这里如果进的时候的dx刚好是csy里的一个
if(car.dx < csy){
col++;
for(int ccf = 1; ccf <= m; ccf++){
if(csy < car.dx && car.dx < csy){
zjcsy++;
cout<<zjcsy<<endl;
break;
}
}
}
}else if(car.stv < v){
sum = ((v*v) - (car.stv * car.stv)) / (2*car.a);
if(car.dx + sum < csy){
col++;
for(int xr = 1; xr <= m; xr++){
if(csy < car.dx && car.dx < csy){
zjcsy++;
cout<<zjcsy<<endl;
break;
}
}
}
}
}else if(car.a < 0){
if(car.stv > v){
sum = ((v*v) - (car.stv*car.stv)) / (2*car.a);
for(int lrz = 1; lrz <= m; lrz++){
if(car.dx <= csy && csy <= (car.dx+sum)){
// cout<<car.dx<<" "<<csy<<" "<<car.dx+sum<<endl;
col++;
zjcsy++;
cout<<zjcsy<<endl;
break;
}
}
// cout<<sum<<endl;
}
}
}
cout<<col<<" ";
for(int sy = 1; sy <= m; sy++){
if(csy != 1){
bsum++;
}
}
cout<<bsum<<endl;
}
}
结构体起手
car数组结构体用来记录车的数量
dx是小车进来的位置
stv是小车初始速度
a是小车加速度
接下来分a==0,a<0,a>0三种情况讨论,看是否超速
1、a=0初速度也小于等于标准速度
2、a<0初速度也小于等于标准速度
3、位移段不跨测试点
均不用判断,因为他们不会超速或超速的那段也测不进去
测试仪用csy数组记录,最后保留一下测试仪个数
有的人可能想每个测试仪都存在数组里,每个加过去
1、每个加过去分类讨论4个5个还硬的过来,10000个呢?更多呢?模不过来
2、有的人考虑为0的,没用的删掉,那有很多大于0的,比如1个、2个也有可能没用的,我注释了“刚好是标准”就是有风险出现这种情况的
所以我们分析下2种情况:
1、我a>0,在某个地方增加达到标准速度,那么这个地方后面所有点肯定超,留最先的测试仪就行
2、我a<0,在某个地方降速达到标准速度,那么这个地方前面至起始位置所有点肯定超,留最后的测试仪就行
最后扫一遍zjcsy就可以得到要留的测试仪
T3
#include<bits/stdc++.h>
#define PII pair<int,int>
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define cl(f,x) memset(f,0x3f,sizeof(f))
using ll = long long;
using namespace std;
const int N=2e5+5,M=1e6+5;
int a,suf,last,n;
ll pre,f;
void solve() {
scanf("%d",&n);
rep(i,1,n) {
scanf("%d",&a);
last]=n+1;
pre=pre+(a==a)*a;
}
per(i,n,1) {
suf=last];
last]=i;
}
suf=n+1;
rep(i,1,n)
f=0;
ll mx=0;
rep(i,1,n) {
chkmax(f,mx+pre);
int p=suf;
if(p<=n)
chkmax(f,f+pre-pre+a);
chkmax(mx,f-pre);
}
printf("%lld\n",mx+pre);
}
int main() {
// freopen("color.in","r",stdin);
// freopen("color.out","w",stdout);
int testcase=1;
scanf("%d",&testcase);
while(testcase--)
solve();
return 0;
}
第三题动态规划
状态转移方程:
dp = max(dp, dp + (a == a ? a : 0));
dp = max(dp, dp + (a == a ? a : 0));
dp = dp + (a == a ? a : 0);
dp = dp + (a == a ? a : 0);
我们最优策略是隔一个选一个,比如5252
我们可以把5都染红2都染蓝,最大权就是7
分析左右染色块推状态转移方程,有数位DP和插头DP的味道
有的同学场下跟我说红黑树后缝个普通DP,维护平衡代码我就不放了,同学们可以自己试试
T4
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define PII pair<int,int>
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define cl(f,x) memset(f,0x3f,sizeof(f))
using ll = long long;
using namespace std;
const int N=1e6+5,M=20;
inline int read() {
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)) {
if(ch=='-')
f=-1;
ch=getchar();
}
while(isdigit(ch))
x=x*10+ch-48,ch=getchar();
return x*f;
}
#define ls(k) (k<<1)
#define rs(k) (k<<1|1)
#define pa(k) (k>>1)
#define sonid(k) (rs(pa(k))==k)
#define bro(k) (k^1)
vector<int> op;
int n,m,k,l,ta,a,b,opp,pos,p,f,g,t;
void dfs(int u,int d) {
++p;
if(d==k) {
t]=u;
pos=p;
return;
}
opp=op];
dfs(ls(u),d+1);
dfs(rs(u),d+1);
}
char s;
void init() {
n=read();
m=read();
rep(i,1,n)
ta=read();
rep(i,1,m)
b=read();
l=1; k=0;
while(l<n)
l<<=1,++k;
per(i,k-1,0) {
scanf("%s",s+1);
int len=strlen(s+1);
op.resize(len+1);
rep(j,1,len)
op=s-48;
}
dfs(1,0);
}
void dfs1(int u,int d) {
if(d==k) {
f=pos;
g=pos-1;
return;
}
dfs1(ls(u),d+1);
dfs1(rs(u),d+1);
if(!opp) {
if(a]>=k-d) {
f=f;
g=g;
} else {
f=f;
g=g;
}
chkmax(g,g);
} else {
if(a]>=k-d) {
f=f;
g=g;
} else {
f=f;
g=g;
}
chkmax(g,g);
}
}
int tc;
ll ans;
void upd(int _l,int _r,int val) {
chkmin(_r,l);
if(_l>_r)
return;
ans+=val;
ans-=val;
}
void solve() {
rep(i,0,3)
tc=read();
rep(i,1,n)
a=ta^tc;
rep(i,n+1,l)
a=INF;
dfs1(1,0);
rep(i,0,l)
ans=0;
rep(i,1,l) {
int u=t,d=0,val=l;
// c >= i
if(i==1)
upd(1,1,i);
while(u!=1) {
int v=pa(u);
++d;
if(opp==sonid(u)) {
if(a<d)
break;
} else {
if(a]>=d)
chkmin(val,g);
}
upd(max(i,(1<<(d-1))+1),min(val,1<<d),i);
u=v;
}
// c < i
u=t; d=0; val=l;
while(u!=1) {
int v=pa(u);
++d;
if(opp!=sonid(u)) {
if(a]>=d)
chkmin(val,g);
}
if(i<=(1<<d)) {
upd((1<<(d-1))+1,min(val,i-1),i);
break;
}
u=v;
}
}
rep(i,1,l)
ans+=ans;
ll res=0;
rep(i,1,m)
res^=i*ans];
printf("%lld\n",res);
}
int main() {
// freopen("arena.in","r",stdin);
// freopen("arena.out","w",stdout);
init();
int testcase=read();
while(testcase--)
solve();
return 0;
}
T4是全国决赛级别的题
差分思想,部分贪心后接DFS,深搜接树形DP
缝缝补补有超时点,各位同学有生log的做法可以在下方留言
最后祝各位rp++,Noip见 用markdown不能直接粘贴,得套上代码标记 苏紫方璇 发表于 2024-11-3 23:43
用markdown不能直接粘贴,得套上代码标记
谢谢谢谢!! Thanks1!
页:
[1]