首页 > 其他分享 >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-02-25 20:58:06浏览次数:19  
标签:std Regional return pt 17 int top Jinan include

Preface

趁着开学前最后一天再凑一场训练,今天这场手感不错前面的题都是一遍过

最后靠着前期的手速7题苟进Au区,后面90min徐神B题没有Rush出来,思路啥都是对的就是一点细节没写好


A. Many Many Heads

首先发现我们可以将所有相邻的同类型括号设为一对,这样一定能得出一个合法的串

考虑将这个括号序列分层处理,最外层可能有若干个子括号对,不难发现当其中出现某种括号的对数\(\ge 2\)就一定有多解

因为这些没有嵌套关系的括号之间互不影响,只要有\(\ge 4\)个位置上有同类型的括号的话那么必然存在大于一种放法

#include <bits/stdc++.h>

std::string s;

int type(int c) { return c == '(' || c == ')'; }

bool check(int &i, int pre) {
    if(i == s.size()) return true;
    if(pre >> type(s[i]) & 1) return false;
    pre |= 1 << type(s[i]);
    int t = i;
    while(type(s[i + 1]) != type(s[i])) i += 1;
    int j = i + 1;
    while(i >= t) {
        if(type(s[i]) != type(s[j])) return false;
        i--; j++;
    }
    return check(i = j, pre);
}

int main() {
    std::ios::sync_with_stdio(false);
    int T; std::cin >> T; while(T--) {
        std::cin >> s;
        int i = 0;
        std::cout << (check(i, 0) ? "Yes\n" : "No\n");
    }
    return 0;
}

B. Graph Partitioning 2

这题大致思路徐神都想到了,但最后没写出来有点可惜

考虑根号分治,当\(k\le \sqrt n\)时,直接记录包含当前子树根节点的连通块大小进行树上背包DP即可

若\(k>\sqrt n\),仍然考虑树上背包,但改为记当前子树内分出的大小为\(k\)的连通块个数,并记录有\(0/1\)个包含当前子树根的大小为\(k+1\)的连通块即可转移

总复杂度\(O(n\sqrt n)\),但代码细节比较多,坐等徐神补题


C. Turn on the Light 2

好难的题,做不来捏、


D. Largest Digit

签到,不难发现当某个区间的大小\(\ge 10\)时则和的个位数一定可以为\(9\);否则直接暴力判断即可

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int t,la,ra,lb,rb;
int main()
{
    for (scanf("%d",&t);t;--t)
    {
        scanf("%d%d%d%d",&la,&ra,&lb,&rb);
        if (ra-la+1>=10||rb-lb+1>=10) { puts("9"); continue; }
        auto calc=[&](int x)
        {
            int ret=0; while (x>0) ret=max(ret,x%10),x/=10; return ret;
        };
        int ans=0; for (RI x=la;x<=ra;++x) for (RI y=lb;y<=rb;++y) ans=max(ans,calc(x+y));
        printf("%d\n",ans);
    }
    return 0;
}

E. I Just Want... One More...

刚开始想简单了但稀里糊涂地过了样例,后面下去反思了下才发现问题过了这个题,差点酿成大祸

首先考虑由源点向左部点连边,右部点向汇点连边,先跑一个最大流出来

考虑如果要新加一条边\(x\to y\),则需要在残量网络上,存在源点到\(x\)的路径以及\(y\)到汇点的路径

根据残量网络的性质,前者等价于从源点开始走剩余容量为\(1\)的边能到达的左部点数;后者等价于从汇点开始走剩余容量为\(0\)的边能到达的右部点数

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<cctype>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005,INF=1e9;
int T,n,m,x,y;
class FileInputOutput
{
    private:
        static const int S=1<<21;
        #define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
        char Fin[S],*A,*B;
    public:
        inline void read(int& x)
        {
            x=0; char ch; while (!isdigit(ch=tc()));
            while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));
        }
}F;
namespace Network_Flow
{
    const int NN=200005,MM=1e7+5;
    struct edge
    {
        int to,nxt,v;
    }e[MM<<1]; int cnt=1,head[NN],cur[NN],dep[NN],s,t;
    inline void addedge(CI x,CI y,CI z)
    {
        e[++cnt]=(edge){y,head[x],z}; head[x]=cnt;
        e[++cnt]=(edge){x,head[y],0}; head[y]=cnt;
    }
    inline void clear(void)
    {
        memset(head,0,(t+1)*sizeof(int)); cnt=1;
    }
    #define to e[i].to
    inline bool BFS(void)
    {
        memset(dep,0,(t+1)*sizeof(int)); dep[s]=1;
        queue <int> q; q.push(s);
        while (!q.empty())
        {
            int now=q.front(); q.pop();
            for (RI i=head[now];i;i=e[i].nxt)
            if (e[i].v&&!dep[to]) dep[to]=dep[now]+1,q.push(to);
        }
        return dep[t];
    }
    inline int DFS(CI now,CI tar,int dis)
    {
        if (now==tar) return dis; int ret=0;
        for (RI& i=cur[now];i&&dis;i=e[i].nxt)
        if (e[i].v&&dep[to]==dep[now]+1)
        {
            int dist=DFS(to,tar,min(dis,e[i].v));
            if (!dist) dep[to]=INF;
            dis-=dist; ret+=dist; e[i].v-=dist; e[i^1].v+=dist;
            if (!dis) return ret;
        }
        if (!ret) dep[now]=0; return ret;
    }
    inline int Dinic(int ret=0)
    {
        while (BFS()) memcpy(cur,head,(t+1)*sizeof(int)),ret+=DFS(s,t,INF); return ret;
    }
};
using namespace Network_Flow;
inline int travel(CI st,CI L,CI R,CI tp)
{
    static int vis[N]; memset(vis,0,(t+1)*sizeof(int));
    queue <int> q; q.push(st); vis[st]=1; int ret=0;
    while (!q.empty())
    {
        int now=q.front(); q.pop(); ret+=(L<=now&&now<=R);
        for (RI i=head[now];i;i=e[i].nxt)
        if (e[i].v==tp) if (!vis[to]) vis[to]=1,q.push(to);
    }
    return ret;
}
#undef to
int main()
{
	//freopen("E.in","r",stdin);
    for (F.read(T);T;--T)
    {
        RI i,j; for (F.read(n),F.read(m),i=1;i<=m;++i)
        F.read(x),F.read(y),addedge(x,y+n,1);
        for (s=2*n+1,t=2*n+2,i=1;i<=n;++i)
        addedge(s,i,1),addedge(i+n,t,1);
        Dinic(); printf("%lld\n",1LL*travel(s,1,n,1)*travel(t,n+1,2*n,0)); clear();
    }
    return 0;
}

F. Say Hello to the Future

啥玩意做不来一点


G. Gifts from Knowledge

很经典的一个题,首先考虑对于两个位置相对的列\(i,c-i+1\),统计这两列中\(1\)的个数

显然若存在\(\ge 3\)个\(1\),则不论怎么操作这两列最后一定存在某列不合法;若存在\(\le 1\)个\(1\),则不论怎么操作都一定合法

现在考虑存在\(2\)个\(1\)的情况,不妨设这两个\(1\)在第\(x,y\)行(允许\(x=y\)),则:

  • 若两个\(1\)在同一列,则第\(x\)行和第\(y\)行有且仅有一行要翻转
  • 若两个\(1\)在不同列,则第\(x\)行和第\(y\)行要么都翻转,要么都不翻转

这是一个经典问题,可以用黑白染色或者拆点+并查集解决,最后方案数就是\(2\)的连通块数量次幂

#include <bits/stdc++.h>

using llsi = long long signed int;
constexpr llsi mod = 1'000'000'007;

llsi ksm(llsi a, llsi b) {
    llsi res = 1;
    while(b) {
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

std::vector<int> fa;
inline int father(int i) {
    if(fa[i] == i) return i;
    return fa[i] = father(fa[i]);
}

void unionn(int a, int b) {
    a = father(a); b = father(b);
    if(a == b) return ;
    fa[b] = a;
}

int work() {
    int n, m; std::cin >> n >> m;
    std::vector<std::string> b(n);
    for(auto &b: b) std::cin >> b;
    fa.resize(2 * n);
    for(int i = 0; i < 2 * n; ++i) fa[i] = i;
    int Tc = 0;
    for(int i = 0; i < m; ++i) {
        int c = 0;
        for(int j = 0; j < n; ++j) c += (b[j][i] == '1');
        if(c > 2) return 0;
        Tc += c; if(Tc > m) return 0;
    }
    for(int l = 0, r = m - 1; l <= r; ++l, --r) {
        std::vector<int> L, R;
        for(int s = 0; s < n; ++s) if(b[s][l] == '1') L.push_back(s);
        for(int s = 0; s < n; ++s) if(b[s][r] == '1') R.push_back(s);
        if(L.size() == 2) unionn(L[0], L[1] + n), unionn(L[0] + n, L[1]);
        if(R.size() == 2) unionn(R[0], R[1] + n), unionn(R[0] + n, R[1]);
        for(auto L: L) for(auto R: R) unionn(L, R), unionn(L + n, R + n);        
    }
    for(int i = 0; i < n; ++i) if(father(i) == father(i + n)) return 0;
    int s = 0;
    for(int i = 0; i < 2 * n; ++i) s += (father(i) == i);
    return ksm(2, s / 2);
}

int main() {
    std::ios::sync_with_stdio(false);
    int T; std::cin >> T; while(T--) std::cout << work() << char(10);
    return 0;
}

H. Basic Substring Structure

看题面像是个字符串就没敢想,后面发现好像是个DS,不管了反正我摆了


I. Strange Sorting

小清新构造题

考虑从前往后还原每个位置,若\(a_i\ne i\)则选定\(i\)作为左端点

不妨找到数\(i\)所在的位置\(j\),显然\(j>i\),同时找到数\(i+1\)所在的位置\(k\)

  • 若\(i<k<j\),则我们操作区间\([i,j]\),那么可以至少同时复原\(i,i+1\)
  • 若\(i<j<k\),那此时\(a_i>a_k\)必然成立,那么我们操作区间\([i,k]\)亦可以同时复原\(i,i+1\)

综上,每次我们可以至少复原\(2\)个数,因此最后操作次数就是\(\frac{n}{2}\)

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

using pii = pair<int, int>;
const int N = 105;
int t, n, A[N];
signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> t;
    while (t--){
        cin >> n;
        for (int i=1; i<=n; ++i) cin >> A[i];
        vector<pii> ans;
        int cur=1;
        while (cur<=n){
            if (A[cur]==cur){++cur; continue;}
            int posa, posb;
            for (int i=cur; i<=n; ++i){
                if (A[i]==cur) posa=i;
                if (A[i]==cur+1) posb=i;
            }
            if (posa>posb) ans.push_back(make_pair(cur, posa)), sort(A+cur, A+posa+1);
            else ans.push_back(make_pair(cur, posb)), sort(A+cur, A+posb+1);
            cur+=2;
        }
        cout << ans.size() << '\n';
        for (auto [a, b] : ans) cout << a << ' ' << b <<'\n';
    }
    return 0;
}

J. Computational Intelligence

最害怕的一题,超级恶心的分类讨论积分题,像我这种高数渣直接一眼寄


K. Rainbow Subarray

刚开始思路想偏了一直在想在差分数组上怎么做,后面祁神直接修改了前提马上就会了这个题

首先不妨将每个\(a_i\)减去\(i\),那么问题转化为找一段区间将其中所有数变成相同的

不难发现对于一个确定的区间,显然将所有数都变成其中位数是最优的

动态求一个集合的中位数是个经典问题,我们拿两个multiset分别维护小于等于中位数的数以及大于等于中位数的数,并保证二者的大小差\(\le 1\)即可

同时要计算贡献的话只要顺带记一下每个multiset内数的和即可,最后在外面套一个尺取法即可\(O(n\log n)\)求解本题

#include<cstdio>
#include<iostream>
#include<set>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=500005;
int t,n,k,a[N];
class Medium_Solver
{
    private:
        multiset <int> A,B; int SA,SB;
    public:
        inline void init(void)
        {
            A.clear(); B.clear(); SA=SB=0;
        }
        inline void insert(CI x)
        {
            if (B.empty())
            {
                B.insert(x); SB+=x; return;
            }
            int mid=*B.begin();
            if (x>=mid)
            {
                B.insert(x); SB+=x;
                if (A.size()<B.size()-1)
                {
                    auto it=B.begin(); SB-=*it; SA+=*it;
                    A.insert(*it); B.erase(it);
                }
            } else
            {
                A.insert(x); SA+=x;
                if (A.size()>B.size())
                {
                    auto it=(--A.end()); SA-=*it; SB+=*it;
                    B.insert(*it); A.erase(it);
                }
            }
        }
        inline void remove(CI x)
        {
            int mid=*B.begin();
            if (x>=mid)
            {
                B.erase(B.find(x)); SB-=x;
                if (A.size()>B.size())
                {
                    auto it=(--A.end()); SA-=*it; SB+=*it;
                    B.insert(*it); A.erase(it);
                }
            } else
            {
                A.erase(A.find(x)); SA-=x;
                if (A.size()<B.size()-1)
                {
                    auto it=B.begin(); SB-=*it; SA+=*it;
                    A.insert(*it); B.erase(it);
                }
            }
        }
        inline int calc(void)
        {
            int mid=*B.begin();
            return (mid*A.size()-SA)+(SB-mid*B.size());
        }
        inline void DEBUG(void)
        {
            for (auto x:A) printf("%lld ",x); printf("SA= %lld\n",SA);
            for (auto x:B) printf("%lld ",x); printf("SB= %lld\n",SB);
        }
}S;
signed main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    for (cin>>t;t;--t)
    {
        RI i,j; for (cin>>n>>k,i=1;i<=n;++i) cin>>a[i],a[i]-=i;
        int ans=0; for (S.init(),i=1,j=0;i<=n;++i)
        {
            while (j<n)
            {
                S.insert(a[++j]);
                //printf("i=%lld j=%lld ans=%lld\n",i,j,S.calc());
                //S.DEBUG();
                if (S.calc()>k) { S.remove(a[j--]); break; }
            }
            ans=max(ans,j-i+1); S.remove(a[i]);
        }
        cout<<ans<<'\n';
    }
    return 0;
}

L. Ticket to Ride

好诡异的题,做不来捏


M. Almost Convex

洒洒水几何题,被祁神一眼秒

直接求出原点集的凸包,考虑把凸包的某个角凹进去是否能得到更优的答案

枚举凹进去的顶点\(a\),转化一下就变成要求找所有三角形\(\triangle abc\)满足其内部没有其它点(其中\(a,b\)为凸包的某条边)

然后这个东西是个很典的问题,转化到夹角上就是个二维偏序问题,直接那单调栈维护一下即可

复杂度\(O(n^2\log n)\)

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

using pii = pair<int, int>;

struct Pt{
    int x, y;
    Pt operator-(Pt b)const{return Pt{x-b.x, y-b.y};}
    int crs(Pt b)const{return x*b.y-y*b.x;}
    bool operator<(Pt b)const{return x!=b.x ? x<b.x : y<b.y;}
};
int cross(Pt p, Pt a, Pt b){return (a-p).crs(b-p);}

const int N = 2e3+5;
int n;
vector<int> CH;
Pt pt[N];
bool inCH[N];

void makeCH(vector<int> &vec){
    int sz = vec.size();
    sort(vec.begin(), vec.end(), [&](int a, int b){return pt[a]<pt[b];});
    // printf("vec:"); for (int xx : vec) printf("(%lld %lld)", pt[xx].x, pt[xx].y);
    vector<int> stk(sz+5); int top=-1;
    stk[++top] = vec[0];
    for (int i=1; i<sz; ++i){
        while (top>0 && cross(pt[stk[top-1]], pt[stk[top]], pt[vec[i]])>=0) --top;
        stk[++top]=vec[i];
    }
    int dn = top;
    for (int i=sz-2; i>=0; --i){
        while (top>dn && cross(pt[stk[top-1]], pt[stk[top]], pt[vec[i]])>=0) --top;
        stk[++top]=vec[i];
    }
    vec.clear(); vec.insert(vec.begin(), stk.begin(), stk.begin()+top);
}

int solve(int x, vector<int> ots){
    int sz=ots.size();
    sort(ots.begin(), ots.end(), [&](int a, int b){return cross(pt[CH[x]], pt[a], pt[b])>0;});
    vector<int> stk(sz+5); int top=0;
    for (int xx : ots){
        while (top>00 && cross(pt[CH[x+1]], pt[xx], pt[stk[top]])>=0) --top;
        stk[++top]=xx;
    }
    return top;
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    CH.resize(n);
    for (int i=0; i<n; ++i){
        cin >> pt[i].x >> pt[i].y;
        CH[i]=i;
    }
    makeCH(CH);
    // printf("CH:"); for (int x : CH) printf("(%lld %lld)", pt[x].x, pt[x].y); puts("");
    vector<int> ots;
    for (int x : CH) inCH[x]=true;
    for (int i=0; i<n; ++i) if (!inCH[i]) ots.push_back(i);

    int sz=CH.size();
    CH.push_back(CH[0]);
    int ans=0;
    for (int i=0; i<sz; ++i){
        ans += solve(i, ots);
        // printf("i=%lld ans=%lld\n", i, ans);
    }
    cout << ans+1 << '\n';
    return 0;
}

Postscript

唉明天就要开学力,美好生活已经结束力

标签:std,Regional,return,pt,17,int,top,Jinan,include
From: https://www.cnblogs.com/cjjsb/p/18033011

相关文章

  • django模型models常用字段24个以及参数17个简要说明
    一、常用字段1、models.AutoField自增列=int(11)如果没有的话,默认会生成一个名称为id的列,如果要显式的自定义一个自增列,必须设置primary_key=True。2、models.CharField字符串字段,必须设置max_length参数3、models.BooleanField布尔类型=tinyint(1)不能为空,可......
  • (17)Lazarus学习之StringGrid1
    01]下拉ComboBox1选择  参考:C:\lazarus\examples\gridexamples\gridcelleditorprocedureTForm1.StringGrid1SelectEditor(Sender:TObject;aCol,aRow:Integer;varEditor:TWinControl);beginif(aCol=3)and(aRow>0)thenbegin//哪些单元格显示Comb......
  • 2017年全年回顾
    本文理论上讲应当在2018年Q1的时候发出来,结果出于各种原因,推迟到了现在。个人收获基于SpringBoot、SpringCloud交付了多个项目,加深了对新技术的理解。上手大数据平台,在交付项目的过程中,学习HBase、Kafka、SparkSQL的调优方法,积累了一定的运维经验。学习架构设计的理论,在项目......
  • Angular Material 17+ 高级教程 – Custom Themes (自定义主题) for Material Design
    前言AngularMaterialv17.2.0发布了MaterialDesign3Theme   上一篇 AngularMaterial17+高级教程–GetStarted下一篇TODO想查看目录,请移步 Angular17+高级教程–目录......
  • 代码随想录算法训练营第二十五天| 216.组合总和III 17.电话号码的字母组合
    组合总和III题目链接:216.组合总和III-力扣(LeetCode)思路:仿照昨天的递归模板写的,同样是for循环横向遍历,递归纵向遍历。注意当k>n时要直接跳出,否则会判断栈溢出。额外发现一个问题就是在累加sum时,用for(autoi:path)sum+=path[i];会出现奇怪数字,原因是auto遍历用法错误,正确写......
  • 洛谷题单指南-贪心-P3817 小A的糖果
    原题链接:https://www.luogu.com.cn/problem/P3817题意分析:吃最少的糖果,保证相邻糖果数之和不大于x,需要某种贪心策略。解题思路:依次遍历相邻两盒糖果如果糖果数之和大于x,必须要吃点一部分,使得糖果数之和刚好等于x贪心策略是:优先吃后一盒糖果,因为这样可以更利于后续的判断成立......
  • 代码随想录算法训练营第二十五天 | 17.电话号码的字母组合 , 216.组合总和III
    216.组合总和III 已解答中等 相关标签相关企业 找出所有相加之和为 n 的 k 个数的组合,且满足下列条件:只使用数字1到9每个数字 最多使用一次返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回......
  • 【更新公告】AirtestIDE更新至1.2.17版本
    1.前言本次更新为AirtestIDE、Airtest-Selenium库更新。AirtestIDE更新至1.2.17版本,AirtestIDE内置库Airtest更新为1.3.3.1版本,Poco更新为1.0.94版本,主要支持了selenium4.0以上版本,ADB更换为41版本,Airtest新增点击和滑动的相对坐标支持,Poco修复了1.0.93运行效率缓慢的问题等......
  • idea创建spring项目的时候只有java 21和17
    1.问题我们在用IDEA创建一个spring项目时,发现java版本只能选用java21,java17,导致我们的jdk版本无法选择jdk1.8(我最常用的版本)2.解决参考:idea创建项目的时候只有java21和17原因是spring2在23年11月24日停止维护了,所以通过spring来创建,没有spring2,只有spring3+,最低jdk版本也是1......
  • Jenkins在jdk17的Tomcat上运行报错
    Jenkins在jdk17的Tomcat上运行报错一、环境宝塔:tomcat8.0jdk:jdk17二、保存项目时报错​Unabletomakefieldprotectedtransientintjava.util.AbstractList.modCountaccessible:modulejava.basedoesnot"opensjava.util"tounnamedmodule@6d15ca84​查看local......