当前位置： 首页 > article >正文

2024 ICPC National Invitational Collegiate Programming Contest, Wuhan Site

article 2024/11/7 10:54:48

tot：赛时就出了三题，罚时343。然后补了两题F,M，再然后过了好一段时间，再补了两题D,E。共计七题。只能说收获不少。

Problem - I - Codeforce--CyclicAppleStringss

思路:队友写的签到题。

//队友写的,签到题
//https://codeforces.com/gym/105143/problem/I
void solve(){
    string s; cin >> s;
    int p = 0, m = 0;
    int sz = s.size();
    for (int i = sz - 1 ; i >= 0; i --) {
        if (s[i] == '0') {
            p = i;
            break;
        }
    }
    for (int i = 0 ; i < sz; i ++) {
        if (s[i] == '1') {
            m = i;
            break;
        }
    }
    if (is_sorted(s.begin(), s.end())) {
        cout << 0 << '\n';
        return ;
    }
//	cout << p << '\n'
    int ans = 0;
    for (int i = m; i <= p; i ++) {
        while (i < p && s[i + 1] == '1') i ++;
        while (i < p && s[i + 1] == '0') i ++;
//		i --;
//		cout << i << '\n';
        ans ++;
    }
    cout << ans << '\n';
}

Problem - K - Codeforces

思路：队友写的，打表找规律。

const int N=2e6+10,M=1e4+10;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
int n;
int a[N];
//队友写的，打表找到规律
//https://codeforces.com/gym/105143/problem/K
void solve(){
    cin >> n;
    if(n%4==3){cout << "Pinkie Pie\n"; return ;}
    else if(n%4==2){cout << "Pinkie Pie\n"; return ;}
    else if(n%4==1){cout << "Fluttershy\n"; return ;}
    else cout << "Fluttershy\n";
}

Problem - B - Codeforces--CountlessMe

思路：

从高位往低位贪心.
很早就发现了n次操作是可以变为任意序列的。
但是一直想歪了,一直在正解的旁边乱搞,各种抽象实现..最后才回到正解.
int n;
int a[200005];
从高位往低位贪心.
很早就发现了n次操作是可以变为任意序列的。
但是一直想歪了,一直在正解的旁边乱搞,各种抽象实现..最后才回到正解.
//https://codeforces.com/gym/105143/problem/B
void solve(){       B
    cin >> n;
    int sum=0;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        sum+=a[i];
    }
    int ans=0;
    for(int i=31;~i;i--){
        int one=1ll<<i;
        if(one>sum) continue;
        int ma=((1ll<<i)-1)*n;
        if(ma<sum){
            ans|=1<<i;
            sum-=min(n,sum/one)*one;
        }
    }
    cout << ans;
}

Problem - F - Codeforces--CustomMadeClothes

思路：已知矩阵a[i][j]>=a[i-1][j] && a[i][j]>=a[i][[j-1]. 很遇到多题了已经,求第k大都和二分相关！

交互题--求一个未知n*n矩阵的第k大
二分答案+技巧的询问--跟暑假写的一题乘法表的二分方法一模一样的!
二分答案然后从左下角到右上角询问,最坏只会问2*n*logn(n*n)=39863<=50000次.
int n,k;
bool check(int cc){
    int x=n,y=1,cnt=0;      //从左下角到右上角
    while(x>=1&&y<=n){
        cout<<"? "<<x<<" "<<y<<" "<<cc<<endl;  //记得注释掉def endl
        int ret; cin>>ret;
        if(ret) cnt+=x,y++;  //maze[x][y]<=cc
        else x--;
    }
    return cnt>=k;      //为什么这里改成cnt<=k,然后下面二分也跟着换位置会wa2?...按理来说是同理的.不懂
}
交互题--求一个未知n*n矩阵的第k大
二分答案+技巧的询问--跟暑假写的一题乘法表的二分方法一模一样的!
//https://codeforces.com/gym/105143/problem/F
void solve(){       F
    cin>>n>>k;
    k=n*n-k+1;  求第k大,即求第n*n-k+1小;这样转化了,才能利用小于等于中的等于号,否则直接求有多少个大于k的话,取不到等号
    int l=1,r=n*n,ans=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)){
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    cout<<"! "<<ans;
}

Problem - M - Codeforces--Merge

思路：

从最大值开始贪心:
①如果最大值x为偶数,那么可以优先造出x+1,得到x+x+1.
如果不能造出x+1,那么再考虑造出x-1,得到x+x-1.
如果都不行,那么考虑次大的数字..
②如果最大值y为奇数,那么y+1和y-1都是偶数,偶数是不可能造出来的(相邻的数相加为奇数),那么直接查询y+1，y-1是否存在即可.
但是会有多次的造数字(例如得到x+x+1之后,还要接着考虑是否存在(x+x+1)+1 or (x+x+1)-1),如何实现? 递归.
hack:
4 -- 1 2 4 8
8 ->7,9
7 <-3+4 , 3<-1+2
这个样例可以体现key1,key2.
如果一直递归下去,太暴力了?  --完全可以,复杂度是o(n*log1e18) 1.2e7
hack,出现数字多用的情况:
最终找到的原因是--getNum考虑到了先cnt--,不行再回溯;但是dfs没有考虑到,dfs也应该先cnt[num]--的,因为无论如何,这个num都要cnt--的,也不用回溯
10 5 1 2 3 6 4 9 8 5 1--good:17 13 5 5 3 1
5 4 3 13 6 3--good:13 13 3
总的来说,还是dfs不熟练,对于递归没有那么精湛,细节注意不到位.
int n;
unordered_map<int,int> cnt;
vector<int> vct,ans;
bool getNum(int need){  //o(log1e18)    此处need只会是奇数
    if(cnt[need]>=1){
        cnt[need]--;
        return true;
    }
    int less=need/2,big=need/2+1;
    if(less%2==0&&cnt[less]>=1){  key:偶数的满足再考虑奇数的
        cnt[less]--;   //key1:先减!
        if(getNum(big)) return true;
        else{
            cnt[less]++;  //key2:如果不行就回溯
            return false;
        }
    }
    else if(big%2==0&&cnt[big]>=1){
        cnt[big]--;  //key1:先减!
        if(getNum(less)) return true;
        else{
            cnt[big]++;  //key2:如果不行就回溯
            return false;
        }
    }
    return false;
}
void dfs(int num){  o(n)
    if(num%2==0){  //num为偶数
        //key:这里要给num+num(+-)1的cnt加上
        cnt[num]--;  key中key:这里要先扣掉,不然剩下数字2,1,1时,2会被使用两次,导致造出一个5.
        debug很久,是这个地方。。上门getNum那里已经想到了要先扣掉,这里又遗漏了这个细节..
        if(getNum(num+1)) cnt[num+num+1]++,dfs(num+num+1);
        else if(getNum(num-1)) cnt[num+num-1]++,dfs(num+num-1);
        else ans.emplace_back(num);
    }
    else{  //num为奇数
        //key:这里要给num+num(+-)1的cnt加上
        if(cnt[num+1]>=1) cnt[num+1]--,cnt[num]--,cnt[num+num+1]++,dfs(num+num+1);
        else if(cnt[num-1]>=1) cnt[num-1]--,cnt[num]--,cnt[num+num-1]++,dfs(num+num-1);
        else cnt[num]--,ans.emplace_back(num);
    }
}
从最大值开始贪心:
①如果最大值x为偶数,那么可以优先造出x+1,得到x+x+1.
如果不能造出x+1,那么再考虑造出x-1,得到x+x-1.
如果都不行,那么考虑次大的数字..
②如果最大值y为奇数,那么y+1和y-1都是偶数,偶数是不可能造出来的(相邻的数相加为奇数),那么直接查询y+1，y-1是否存在即可.
但是会有多次的造数字(例如得到x+x+1之后,还要接着考虑是否存在(x+x+1)+1 or (x+x+1)-1),如何实现? 递归.
//hack:
//4 -- 1 2 4 8
//8 ->7,9
//7 <-3+4 , 3<-1+2
//这个样例可以体现key1,key2.
//如果一直递归下去,太暴力了?  --完全可以,复杂度是o(n*log1e18) 1.2e7
//hack,出现数字多用的情况:
最终找到的原因是--getNum考虑到了先cnt--,不行再回溯;但是dfs没有考虑到,dfs也应该先cnt[num]--的,因为无论如何,这个num都要cnt--的,也不用回溯
//10 5 1 2 3 6 4 9 8 5 1--good:17 13 5 5 3 1
//5 4 3 13 6 3--good:13 13 3
总的来说,还是dfs不熟练,对于递归没有那么精湛,细节注意不到位.
//https://codeforces.com/gym/105143/problem/M
void solve(){       M-merge
    cin>>n;
    for(int i=1;i<=n;i++){
        int x; cin>>x;
        cnt[x]++,vct.emplace_back(x);
    }
    sort(vct.begin(),vct.end(),greater<int>());
    for(auto v:vct){
        if(cnt[v]<=0) continue;
        dfs(v);
    }
    cout<<ans.size()<<endl;
    for(auto a:ans) cout<<a<<" ";
}

Problem - E - Codeforces--Boomerang

思路：

一直加叶子节点,动态维护树的直径,不能按照root求出初始的直径,然后就认为这样是最长的了.实际上直径的长度有可能会改变,并且不经过root.
debug了半天才发现错例,发现直径是会变的,并且可能不经过root.一直都认为直径是经过root的那条..再改吧.
key:众所周知的结论是距离树上某节点最远的点一定为当前直径的端点，
即加入x后新的直径仅可能是(u,v),(u,x),(x,v)三者之一，套路地求lca即可得到路径长度。
那么可以求出各个时刻的直径长度,对于每个k可以进行二分,O(1)查询此时刻的直径长度.
int n;
vector<int> vct[200005];
int root,t0;
int dep[200005];
int fa[200005][20];
vector<bool> vis(200005,false);
void dfs(int u,int father){ //初始化出dep和fa
    dep[u]=dep[father]+1;
    fa[u][0]=father;
    for(int i=1;i<20;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(auto v:vct[u]) if(v!=father) dfs(v,u);
}
inline int lca(int u,int v){
    if(dep[v]>dep[u]) swap(u,v); //让深的往上跳
    for(int i=19;i>=0;i--) if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
    if(u==v) return u;
    for(int i=19;i>=0;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
int dist(int u,int v){ return dep[u]+dep[v]-2*dep[lca(u,v)]; } //求树中任意两点距离.
vector<int> len;
inline bool check(int x,int k){
    int len0=0;
    if(x>=(int)len.size()-1) len0=len[(int)len.size()-1];
    else len0=len[x];
    return len0/2<=(x-t0)*k;
}
//一直加叶子节点,动态维护树的直径,不能按照root求出初始的直径,然后就认为这样是最长的了.实际上直径的长度有可能会改变,并且不经过root.
//debug了半天才发现错例,发现直径是会变的,并且可能不经过root.一直都认为直径是经过root的那条..再改吧.
key:众所周知的结论是距离树上某节点最远的点一定为当前直径的端点，
即加入x后新的直径仅可能是(u,v),(u,x),(x,v)三者之一，套路地求lca即可得到路径长度。
那么可以求出各个时刻的直径长度,对于每个k可以进行二分,O(1)查询此时刻的直径长度.
//Boomerang
//https://codeforces.com/gym/105143/problem/E
void solve(){   //E
    cin>>n;
    for(int i=1;i<=n-1;i++){
        int u,v; cin>>u>>v;
        vct[u].emplace_back(v);
        vct[v].emplace_back(u);
    }
    cin>>root>>t0;
    if(n==1){ cout<<t0<<endl; return; }  //特判!!
    dfs(root,0);
    int ept1=root,ept2=root; //endPoint
    vis[root]=true;
    queue<int> que;
    que.emplace(root);
    int d=2; //d从2开始
    len.emplace_back(0);
    while(!que.empty()){        //层序遍历
        if(dep[que.front()]>d) {
            len.emplace_back(dist(ept1,ept2)+1);
            d++;
        }
        int from=que.front();
        que.pop();
        if(dist(from,ept1)>dist(ept1,ept2)) ept2=from;
        else if(dist(from,ept2)>dist(ept1,ept2)) ept1=from;
        for(auto v:vct[from]) if(!vis[v]) que.emplace(v),vis[v]=true;
    }
    len.emplace_back(dist(ept1,ept2)+1);
//    for(int i=1;i<len.size();i++) cout<<len[i]<<" ";
    for(int k=1;k<=n;k++){
        int l=t0+1,r=1e8,res=t0;
        while(l<=r){
            int mid=(l+r)>>1;
            if(check(mid,k)){
                res=mid;
                r=mid-1;
            }
            else l=mid+1;
        }
        cout<<res<<" ";
    }
}
//31
//1 2
//2 3
//3 4
//4 5
//5 6
//6 7
//7 20
//3 8
//8 9
//8 21
//21 22
//22 23
//4 24
//24 25
//25 28
//25 29
//4 26
//26 27
//27 30
//27 31
//5 15
//15 16
//16 17
//15 18
//18 19
//5 10
//10 13
//13 14
//10 11
//11 12
//25 3
//expect:8 5 4... output:7 5 4...

Problem - D - Codeforces--ICPC

思路：

说是简单二维dp,但是看了很久很久(dp还是太差劲),终于懂多了..
首先很明显的是,要么不拐弯,要么只有一次拐弯.
那么可以预处理出数组g[s][t]:起始位置为s,不拐弯,走t步可得最大的价值.
再从左往右,和右往左更新,枚举拐弯一次的情况--key
最关键的是:这个dp过程,怎么取到先左走三(多)个,再往右一直走的情况?
dp[s][t]=max(dp[s-1][t-1],g[s][t]); 这里的dp[s-1][t-1]是有传递性的,不只是说往左走一步然后往右一直走;
dp[s-1][t-1]这个状态可能是由dp[s-2][t-2]转移过来的..
以此类推,那么无论是先往左/右走多少步,再往另一个方向一直走都会覆盖到,所以是不会漏状态的...
好一个传递性....多写多思考多收获..
int n;
int pre[5003];
//1024mb..5e7+5e7能开.
int g[5003][2*5003];  //g[s][t]定义为:起始点为s,可走t步,不拐弯,可得的最大代价.
int dp[5003][2*5003]; //dp[s][t]定义为:起始点为s,可走t不,可拐弯,可得的最大代价.
//参考题解:
//https://blog.csdn.net/Lazy_ChessPlayer/article/details/138479914 --这个写的好很多,通俗易懂.
//https://zhuanlan.zhihu.com/p/696036772
//说是简单二维dp,但是看了很久很久(dp还是太差劲),终于懂多了..
//首先很明显的是,要么不拐弯,要么只有一次拐弯.
//那么可以预处理出数组g[s][t]:起始位置为s,不拐弯,走t步可得最大的价值.
//再从左往右,和右往左更新,枚举拐弯一次的情况--key
最关键的是:这个dp过程,怎么取到先左走三(多)个,再往右一直走的情况?
dp[s][t]=max(dp[s-1][t-1],g[s][t]); 这里的dp[s-1][t-1]是有传递性的,不只是说往左走一步然后往右一直走;
dp[s-1][t-1]这个状态可能是由dp[s-2][t-2]转移过来的..
以此类推,那么无论是先往左/右走多少步,再往另一个方向一直走都会覆盖到,所以是不会漏状态的...
好一个传递性....多写多思考多收获..
//https://codeforces.com/gym/105143/problem/D
void solve(){       //D
    cin>>n;
    for(int i=1;i<=n;i++) cin>>pre[i],pre[i]+=pre[i-1];
    //通过前缀和预处理出不拐弯情况下的可得最大价值.
    for(int s=1;s<=n;s++){
        for(int t=0;t<=2*n;t++){
            int l=max(0ll,s-t);
            int r=min(n,s+t);
            g[s][t]=max(pre[s]-pre[l-1],pre[r]-pre[s-1]);
        }
    }
    //往右走,向左拐弯.
    for(int s=1;s<=n;s++){
        for(int t=1;t<=2*n;t++){
            //往左拐 or 直走
            dp[s][t]=max(dp[s-1][t-1],g[s][t]);
        }
    }
    //往左走,向右拐弯.
    for(int s=n;s>=1;s--){
        for(int t=2*n;t>=1;t--){
            //往右拐 or 直走
            dp[s][t]=max(dp[s][t],dp[s+1][t-1]); //往右拐不一定比当前更优
            dp[s][t]=max(dp[s][t],g[s][t]);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        int res=0;
        for(int j=1;j<=2*n;j++) {
            res^=(j*dp[i][j]);
//            cout<<dp[i][j]<<" ";
        }
//        cout<<endl;
        ans^=(i+res);
    }
    cout<<ans;
    cout<<2*1000*log2(1e6);
}


http://www.kler.cn/a/382871.html

相关文章：

  • 2020年美国总统大选数据分析与模型预测
  • 论文阅读笔记：Image Processing GNN: Breaking Rigidity in Super-Resolution
  • OpenCV视觉分析之目标跟踪(12)找到局部的最大值函数meanShift()的使用
  • 「Mac畅玩鸿蒙与硬件25」UI互动应用篇2 - 计时器应用实现
  • 探索PickleDB：Python中的轻量级数据存储利器
  • git创建分支
  • 套利定理
  • 路见不平 ！ 基于tensorlfow快速迭代的户型图分类功能
  • pycharm 使用
  • 高考数学之圆锥曲线知识要点
  • 【ChatGPT】搜索趋势分析
  • 七、Spring Boot集成Spring Security之前后分离认证最佳实现
  • 智能化健身房管理：Spring Boot与Vue的创新解决方案
  • 《C++ 游戏开发》
  • Unity中c#脚本使用protocol buffers
  • 制作并量化GGUF模型上传到HuggingFace和ModelScope
  • [C++ 核心编程]笔记 4.4.1 全局函数做友元
  • 51c嵌入式~合集1
  • openvino python推理demo
  • 网络,NAT地址转换,虚拟路由冗余协议VRRP
  • Linux云计算 |【第五阶段】CLOUD-DAY8
  • Java 批量导出Word模板生成ZIP文件到浏览器默认下载位置
  • 大模型与搜索引擎结合：智能体、思维链和智谱AI搜索代码案例
  • w~视觉~3D~合集1
  • LeetCode题练习与总结：O(1) 时间插入、删除和获取随机元素--380
  • xshell连接不上linux的原因