首页 > 其他分享 >The 2023 ICPC Asia Jinan Regional Contest (The 2nd Universal Cup. Stage 17: Jinan)

The 2023 ICPC Asia Jinan Regional Contest (The 2nd Universal Cup. Stage 17: Jinan)

时间:2024-09-29 14:38:16浏览次数:8  
标签:Regional return 17 val int siz Jinan 中位数 maxn

赛时4题,策略重大失误,g题思路假了但是以为是代码问题硬调3.5h,m题本来是可以过的,e是网络流说不定也能过呢。
xixike大力平衡树直接打过k题省去思考双优先队列算法的时间,太强

A

观察到同级同形状括号如果有四个就一定可以交换顺序,而且是充要的,经典括号匹配用栈存储就过了,我代码比较丑

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
struct Node{
    bool shp=0;
    int ji=0;
}sta[maxn];
bool vis[maxn][2];

int main(){
    int t;cin>>t;while(t--){
        string s;cin>>s;
        int k=0,tot=0;
        bool ans=0;
        for(int i=0;i<s.size();i++){
            if(s[i]=='('||s[i]==')'){
                if(
                    tot==0)sta[tot].ji=++k,sta[tot].shp=1,tot++;
                else if(sta[tot-1].shp==0)sta[tot].ji=++k,sta[tot].shp=1,tot++;
                else{
                    int tmp=sta[tot-1].ji,tmp1=sta[tot-1].shp;
                    if(vis[tmp][tmp1]){
                        ans=1;break;
                    }
                    else  vis[tmp][tmp1]=1;
                    tot--;k=tmp-1;
                }
            }
            else{
                if(tot==0)sta[tot].ji=++k,sta[tot].shp=0,tot++;
                else if(sta[tot-1].shp)sta[tot].ji=++k,sta[tot].shp=0,tot++;
                else{
                    int tmp=sta[tot-1].ji,tmp1=sta[tot-1].shp;
                    if(vis[tmp][tmp1]){
                        ans=1;break;
                    }
                    else  vis[tmp][tmp1]=1;
                    tot--;k=tmp-1;
                }
            }
        }
        int n=s.size();
        for(int i=0;i<=n;i++)vis[i][0]=0,vis[i][1]=0,sta[i].ji=0,sta[i].shp=0;
        if(ans)cout<<"NO"<<endl;
        else cout<<"Yes"<<endl;
    }
}

K

思路是首先发现区间一定取最大的,就可以双指针操作,只要操作次数小于k就合法,可以继续移动指针r,否则移动l。计算是难点,首先先预处理-0,-1,-2,把每个数的差值减掉,然后每个数就只需要再减去中位数即可。这个中位数其实是l,r区间的中位数因为显然如果不是中位数的话操作次数一定会+x(离中位数的距离),所以不优。然后每次插入一个数中位数只会移动一下所以也是可以维护小于中位数的数和大于中位数的数计算的。
队友写的平衡树(multiset显然也能写)

#define ll long long
#define int long long

using namespace std;

const int N = 5e5 + 10;
int T, n;
ll k;
int a[N];

int ls[N], rs[N], val[N];
int wei[N], siz[N];

inline void pushup(int x){
    siz[x] = siz[ls[x]] + siz[rs[x]] + 1;
}

inline void split(int x, int k, int &a, int &b){
    if(!x) return a = b = 0, void();
    if(val[x] <= k) a = x, split(rs[x], k, rs[x], b);
    else b = x, split(ls[x], k, a, ls[x]);
    pushup(x);
}

inline int merge(int x, int y){
    if(!x || !y) return x | y;
    if(wei[x] <= wei[y]){
        rs[x] = merge(rs[x], y);
        return pushup(x), x;
    }else{
        ls[y] = merge(x, ls[y]);
        return pushup(y), y;
    }
}

int rt, tot;

inline int newnode(int k){
    siz[++tot] = 1, val[tot] = k, wei[tot] = rand();
    return tot;
}

inline void ins(int k){
    int a, b; split(rt, k, a, b);
    rt = merge(merge(a, newnode(k)), b);
}

inline void del(int k){
    int a, b, c; split(rt, k, a, b); split(a, k - 1, a, c);
    c = merge(ls[c], rs[c]), rt = merge(merge(a, c), b);
}

inline int kth(int x, int k){
    if(k == siz[ls[x]] + 1) return val[x];
    if(k > siz[ls[x]] + 1) return kth(rs[x], k - siz[ls[x]] - 1);
    else return kth(ls[x], k);
}

inline void solve(){
    cin >> n >> k;
    for(int i = 1; i <= n; ++i) siz[i] = val[i] = wei[i] = ls[i] = rs[i] = 0;
    for(int i = 1; i <= n; ++i) cin >> a[i], a[i] -= i;

    rt = tot = 0;
    int dlt = 0, val = 0, tmp = 0, ans = 0;
    for(int l = 1, r = 1; r <= n; ++r){
        // cout << l << " " << r << endl;
        // int w = a[r] - dlt;
        ins(a[r]), dlt++;
        // cout << "? " << (r - l + 1 + 1) / 2 << endl;
        int ak = kth(rt, (r - l + 1 + 1) / 2);
        // cout << "aj " << l << " " << r << " " << ak << " " << val << endl;
        if(ak == val){
            tmp += abs(a[r] - val);
        }else{
            if(!(siz[rt] & 1)){
                // cout << "? " << val << endl;
                tmp += abs(a[r] - val);
            }else tmp += abs(a[r] - ak);
                val = ak;
        }
        while(tmp > k){
            del(a[l]);
            ak = kth(rt, (r - l + 1 + 1) / 2);
            if(ak == val) tmp -= abs(a[l] - val);
            else{
                if(siz[rt] & 1) tmp -= abs(ak - a[l]);
                else tmp -= abs(val - a[l]);
                val = ak;
            }
            l++;
        }
        if(tmp <= k) ans = max(ans, r - l + 1);
    }
    cout << ans << endl;
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    ios :: sync_with_stdio(false);
    cin >> T;
    while(T--) solve();
    return 0;
}

G

最搞笑的一题。
一开始搞染色后面以为是2-sat最后发现小丑。首先要观察到01,11这两种1的情况,然后对于两个有限制关系的操作想到建图,主要问题是要把选和不选建成两个点(赛时就是没这样做直接假了),然后并查集不建图宝宝也能过。(我写法建图的)

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
const int maxn=2e6+10,mod=1e9+7;

int n,m,vis[maxn],k;
vector<int>E[maxn];
string s[maxn];

void mul(int &x,int y){x=1ll*x*y%mod;}

void dfs(int x){
    vis[x]=k;//cout<<x<<' '<<vis[x]<<endl;
    for(auto y:E[x]){
        if(!vis[y])dfs(y);
    }
    return;
}

void solve(){
    cin>>n>>m;k=0;
    for(int i=1;i<=2*n;i++)E[i].clear(),vis[i]=0;
    for(int i=1;i<=n;i++)cin>>s[i],s[i]=" "+s[i];
    //建图
    for(int i=1;i<=m/2;i++){
        int u=0,v=0,cnt=0;
        for(int j=1;j<=n;j++){
            if(s[j][i]=='1'){
                if(u)v=j;
                else u=j;
                cnt++;
            }
            if(s[j][m-i+1]=='1'){
                if(u)v=j;
                else u=j;
                cnt++;
            }
        }
        if(u&&v&&u!=v){
            if(s[u][i]!=s[v][i]){
                E[u].pb(v);E[v].pb(u);
                E[u+n].pb(v+n);E[v+n].pb(u+n);
            }
            else{
                E[u].pb(v+n);E[v+n].pb(u);
                E[u+n].pb(v);E[v].pb(u+n);
            }
        }
        if(cnt>2)return cout<<0<<endl,void();
    }
    if(m&1){
        int cnt=0;
        for(int i=1;i<=n;i++)if(s[i][m/2+1]=='1')cnt++;
        if(cnt>1)return cout<<0<<endl,void();
    }

    int ans=1;
    for(int i=1;i<=n*2;i++){
        if(!vis[i])++k,dfs(i);
    }
    k/=2;for(int i=1;i<=k;i++)mul(ans,2);
    for(int i=1;i<=n;i++){
        if(vis[i]==vis[i+n])ans=0;
    }
    cout<<ans<<endl;
}
signed main(){
    int t;cin>>t;while(t--){
        solve();
    }
}

标签:Regional,return,17,val,int,siz,Jinan,中位数,maxn
From: https://www.cnblogs.com/lyrrr/p/18439668

相关文章

  • java 警告:源发行版17 需要目标发行版17
    问题:在从网上复制的项目想要在本地部署,或者本地有多个jdk版本,在开启项目时容易出现jdk版本不一致的问题,导致项目不能运行起来。解决:解决这种问题主要时修改各个模块的jdk版本,使之一致。即确保以下几个地方的版本一致1、在ProjectStructure的Project下确保SDK和Languagel......
  • 学期2024-2025-1 学号 20241317 《计算机基础与程序设计》第1周学习总结
    这个作业属于哪个课程 https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP这个作业要求在哪里 https://www.cnblogs.com/rocedu/p/9577842.html#WEEK01这个作业的目标 1.基于VirtualBox虚拟机安装Ubuntu和安装Linux系统2.快速浏览一遍教材计算机科学概论(第七版),课本每章提......
  • CS 417/517: Introduction to Human Computer Interaction
    CS417/517:IntroductiontoHumanComputerInteraction Project1(Fall2024)1IntroductionInthisassignment,yourtaskistoimplementaConvolutionalNeuralNetwork(CNN)andevaluatetsperformanceinclassifyinghandwrittendigits.Aftercompleti......
  • 如何用Python的Seaborn库绘制17个超好看图表!
    Seaborn简介定义Seaborn是一个基于matplotlib且数据结构与pandas统一的统计图制作库。Seaborn框架旨在以数据可视化为中心来挖掘与理解数据。优点代码较少图形美观功能齐全主流模块安装pip命令安装从github安装流程导入绘图模块提供显示条件导入数据设......
  • java 17 查看 运行时内存堆 的命令
    Java17Windows11- 发生问题运行了一个java程序,基于Java17的。在使用jmap查看堆内存分配时,出现了错误:>jmap-heap8400Error:-heapoptionusedCannotconnecttocoredumporremotedebugserver.Usejhsdbjmapinstead提示使用jhsdbjamp替代。ben......
  • [ABC176F] Brave CHAIN
    [ABC176F]BraveCHAIN题意给你\(3n\)个数字。每次你可以选取前\(5\)个数字,拿走里面任意三个数字,剩下两个,如果拿走的\(3\)个数字相等,得分\(+1\)。问最大得分是多少。思路首先我们想尝试贪心。然而不好贪心,因为你不知道前面会给你留下哪两张牌,留下的方案数很多。题目......
  • ctfshow-web-信息搜集(11-17)
    web11题目提示:域名其实也可以隐藏信息,比如ctfshow.com就隐藏了一条信息。原理:通过Dns检查查询Flag。这里可以用阿里云的网站:Dns查询网站:阿里云网站运维检测平台(aliyun.com)web12题目提示:有时候网站上的公开信息,就是管理员常用密码原理:查看robots.txt文件,找到后台登录页......
  • [NOIP2017 提高组] 奶酪 题解
    题目背景NOIP2017提高组D2T1题目描述现有一块大奶酪,它的高度为 h,它的长度和宽度我们可以认为是无限大的,奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系,在坐标系中,奶酪的下表面为 z=0,奶酪的上表面为 z=h。现在,奶酪的下表面有一只小老鼠Jerry,......
  • 【洛谷】AT_abc178_d [ABC178D] Redistribution 的题解
    【洛谷】AT_abc178_d[ABC178D]Redistribution的题解洛谷传送门AT传送门题解一个水水的动态规划,阿巴巴巴。题目大概是这样:给定一个正整数SSS,问有多少个数满足以......
  • 17、网络安全合规审查五大内容
    数据来源:3.网络安全合规审查五大内容_哔哩哔哩_bilibili网络安全合规审查内容网络安全等级保护的合规审查检查网络系统是否符合相应的安全等级要求,确保等级保护措施到位。关键基础信息设施安全的合规审查评估关键基础设施的安全防护措施和管理制度,确保其安全性和稳定性。......