2024 CCPC Liaoning Provincial Contest

🕗 发布于 2024-11-07 10:11 c++ ccpc

tot：赛时是6题723罚时，还是差劲了。省赛，特别是这场省赛，难度低很多。前面4，5题都是签到题。第六题是一个关于闰年的容斥，脑子乱了，然后越来越绕。然后就没出。出的是一个诈骗题，题面引导你这是计算几何，但是实际上是简单dp，暴力o(n^2)预处理一下就行了。赛时还想着求凸包然后旋转卡壳求凸包直径来预处理，再dp，但是这样是o(n^3)的，然后过了不知道多久突然才发现完全用不上计算几何，直接最普通的枚举区间取max就可以预处理出来了。然后赛后再补了闰年的容斥和一题挺典型的题目，共计8题。

2024CCPC辽宁省赛.pdf

比分幻术

思路：签到。

string str;
void solve(){
    cin>>str;
    cout<<str[2]<<str[1]<<str[0];
}

爱上字典

思路：签到。

string str;
int n;
string toLower(string s){
    int len=(int)s.size();
    string res="";
    for(int i=0;i<len;i++){
        if(s[i]>='A'&&s[i]<='Z') res+=s[i]+32;
        else res+=s[i];
    }
    return res;
}
void solve(){   //A
    getline(cin,str);
    str=toLower(str);
    cin>>n;
    unordered_map<string,bool> mp;
    for(int i=1;i<=n;i++){
        string s; cin>>s;
        mp[toLower(s)]=true;
    }
    string cur="";
    int ans=0;
    for(int i=0;i<(int)str.size();i++){
        if(str[i]>='a'&&str[i]<='z') cur+=str[i];
        else if(cur!=""){
            if(!mp[cur]) ans++,mp[cur]=true;
            cur="";
        }
    }
    cout<<ans;
}

结课风云

思路：签到。

int n,a,b,c,d;
int x[1003],y[1003];
void solve(){       //J
    cin>>n>>a>>b>>c;
    for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
    cin>>d;
    int ans=0;
    for(int i=1;i<=n;i++){
        if(x[i]+y[i]>=c) continue;
        x[i]=min(a,x[i]+d);
        if(x[i]+y[i]>=c) ans++;
    }
    cout<<ans;
}

插排串联

思路：用multiset存一下每个排插的大小，然后在回溯的时候判断是否有满足条件的排插即可。

int n;
int arr[100005];
vector<int> vct[100005];
multiset<int> st;  //用了set,给去重了。。不能去重。。
bool ans=true;
int dfs(int s){
    if((int)vct[s].size()==0) return arr[s];
    int res=0;
    for(auto v:vct[s]) res+=dfs(v);
    if(s==0&&res>2200) ans=false;
    else if(s==0) return 0;
    auto p=st.lower_bound(res);
    if(p==st.end()) ans=false;
    else st.erase(p);
    return res;
}
void solve(){       //C
    cin>>n;
    for(int i=1;i<=n;i++){
        int x; cin>>x>>arr[i];
        vct[x].emplace_back(i);
    }
    for(int i=1;i<=n;i++) if((int)vct[i].size()!=0) st.emplace(arr[i]);
    dfs(0);
    ans?cout<<"YES":cout<<"NO";
}

都市叠高

思路：题目误导你这题是计算几何，实则只是普通的dp。一开始的确被误导了，很后面才反应过来o(n^2)就能预处理出要的信息了。简单dp。

int n;
typedef struct Point{
    int x,y;
}Point;
Point point[5005];
double dist(Point a,Point b){ return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) ); }
double dp[5005];
double mx[5005][5005];  //dist[i][j]定义为:从i往后连续j个构成的凸包直径.
void solve(){
    cout<<setprecision(10);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>point[i].x>>point[i].y;
    for(int i=1;i<=n;i++){
        double mx0=0;
        for(int j=i+1;j<=n;j++){
            mx0=max(mx0,dist(point[i],point[j]));
            mx[i][j]=mx0;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            dp[i]=max(dp[i],dp[i-j]+mx[i-j+1][i]);
        }
    }
    cout<<dp[n];
}

俄式简餐

思路：队友写的构造。注意判6的情况就行。

void solve(){       //E
    int n, m;
    cin >> n >> m;
    vector g(n + 10, vector<int>(m + 10));
    int cnt = 1;
    if (n == 2 && m == 2 || n * m % 4) {
        cout << "NO" << endl;
        return ;
    }
    if (n % 4 == 0) {
        for (int j = 1; j <= m; j ++) {
            for (int i = 1; i <= n; i += 4) {
                g[i][j] = g[i + 1][j] = g[i + 2][j] = g[i + 3][j] = cnt;
                cnt ++;
            }
        }
    } else if (m % 4 == 0) {
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= m; j += 4) {
                g[i][j] = g[i][j + 1] = g[i][j + 2] = g[i][j + 3] = cnt;
                cnt ++;
            }
        }
    } else if ( n % 2 == 0 && m % 2 == 0) {
        if (n % 6 == 0) {
            for (int j = 1; j <= m; j += 2) {
                for (int i = 1; i <= n; i += 6) {
                    g[i][j] = g[i][j + 1] = g[i + 1][j] = g[i + 2][j] = cnt++;
                    g[i + 3][j] = g[i + 4][j] = g[i + 5][j] = g[i + 5][j + 1] = cnt ++;
                    g[i + 1][j + 1] = g[i + 2][j + 1] = g[i + 3][j + 1] = g[i + 4][j + 1] = cnt ++;
                }
            }
        } else if (n % 6 == 4) {
            for (int j = 1; j <= m; j += 2) {
                for (int i = 1; i <= n - 4; i += 6) {
                    g[i][j] = g[i][j + 1] = g[i + 1][j] = g[i + 2][j] = cnt++;
                    g[i + 3][j] = g[i + 4][j] = g[i + 5][j] = g[i + 5][j + 1] = cnt ++;
                    g[i + 1][j + 1] = g[i + 2][j + 1] = g[i + 3][j + 1] = g[i + 4][j + 1] = cnt ++;
                }
            }
            for (int j = 1; j <= m; j ++) {
                g[n][j] = g[n - 1][j] = g[n - 2][j] = g[n - 3][j] = cnt;
                cnt ++;
            }
        } else if (m % 6 == 0) {
            for (int i = 1; i <= n; i += 2) {
                for (int j = 1; j <= m; j += 6) {
                    g[i][j] = g[i + 1][j] = g[i][j + 1] = g[i][j + 2] = cnt++;
                    g[i][j + 3] = g[i][j + 4] = g[i][j + 5] = g[i + 1][j + 5] = cnt ++;
                    g[i + 1][j + 1] = g[i + 1][j + 2] = g[i + 1][j + 3] = g[i + 1][j + 4] = cnt ++;
                }
            }
        } else if (m % 6 == 4) {
            for (int i = 1; i <= n; i += 2) {
                for (int j = 1; j <= m - 4; j += 6) {
                    g[i][j] = g[i + 1][j] = g[i][j + 1] = g[i][j + 2] = cnt++;
                    g[i][j + 3] = g[i][j + 4] = g[i][j + 5] = g[i + 1][j + 5] = cnt ++;
                    g[i + 1][j + 1] = g[i + 1][j + 2] = g[i + 1][j + 3] = g[i + 1][j + 4] = cnt ++;
                }
            }
            for (int i = 1; i <= n; i ++) {
                g[i][m] = g[i][m - 1] = g[i][m - 2] = g[i][m - 3] = cnt;
                cnt ++;
            }
        } else if (n % 4 == 2 && n != 2) {
            for (int j = 1; j <= m; j ++) {
                for (int i = 1; i <= n - 6; i += 4) {
                    g[i][j] = g[i + 1][j] = g[i + 2][j] = g[i + 3][j] = cnt ++;
                }
            }
            for (int j = 1; j <= m; j += 2) {
                g[n - 5][j] = g[n - 4][j] = g[n - 3][j] = g[n - 5][j + 1] = cnt ++;
                g[n - 2][j] = g[n - 1][j] = g[n][j] = g[n][j + 1] = cnt ++;
                g[n - 4][j + 1] = g[n - 3][j + 1] = g[n - 2][j + 1] = g[n - 1][j + 1] = cnt ++;
            }
        } else if (m % 4 == 2) {
//            cout << "------" << endl;
            for (int i = 1; i <= n; i ++) {
                for (int j = 1; j <= m - 6; j += 4) {
                    g[i][j] = g[i][j + 1] = g[i][j + 2] = g[i][j + 3] = cnt;
                    cnt ++;
                }
            }
            for (int i = 1; i <= n; i += 2) {
                g[i][m - 5] = g[i][m - 4] = g[i][m - 3] = g[i + 1][m - 5] = cnt ++;
                g[i][m - 2] = g[i][m - 1] = g[i][m] = g[i + 1][m] = cnt ++;
                g[i + 1][m - 4] = g[i + 1][m - 3] = g[i + 1][m - 2] = g[i + 1][m - 1] = cnt ++;
            }
        }
    }
    cout << "YES" << endl;
//    return ;
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            cout << g[i][j] << ' ';
        }
        cout << endl;
    }
}

龙之研习

思路：

n 整除 4×100^p 但不整除 100^(p+1);
式子①:x/4*100^p;
式子②:x/100^(p+1);
这里①是:x整除4*100^p的都是闰年,但是其中②是平年,所以要减去.
同时,②还有去重的作用,因为下一个p是:x/4*100^(p+1),这里的x/4*100^(p+1)按理来说已经被上一个算过了
但是因为上一个同时还有②,那么会把属于x/4*100(p+1)的部分给减去了,同时更高次方的也会减去..
其他的次方是同理的,如此下来,是没有算重算漏的.

int n;
inline int cal(int x){  //计算2025~x的平年的个数
    int run=0,run0=0,x0=2024,q=1;
    for(int p=0;p<=8;p++){
        // n 整除 4×100^p 但不整除 100^(p+1);
        //式子①:x/4*100^p;
        //式子②:x/100^(p+1);
        //这里①是:x整除4*100^p的都是闰年,但是其中②是平年,所以要减去.
        //同时,②还有去重的作用,因为下一个p是:x/4*100^(p+1),这里的x/4*100^(p+1)按理来说已经被上一个算过了
        //但是因为上一个同时还有②,那么会把属于x/4*100(p+1)的部分给减去了,同时更高次方的也会减去..
        //其他的次方是同理的,如此下来,是没有算重算漏的.
        run+=x/(4*q)-x/(q*100);
        run0+=x0/(4*q)-x0/(q*100);
        q*=100;
    }
    return (x-run)-(x0-run0);
}
void solve(){
    cin>>n;
    int l=2025,r=4e18,ans=-1;
    while(l<=r){
        int mid=(l+r)>>1ll;
        if(cal(mid)>=n){  //这里得是>=号,不然可能取不到最小值..也不能直接对(ans,mid)取min.
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    cout<<ans<<endl;
}

顾影自怜

思路：

不懂不懂..没思路...一开始想着很混乱,最大值是不同数字,又是隔开的,又是区间的,还要满足k个..晕..
key:这个时候就要考虑,需要什么信息?可以预处理出来吗?
①也不难..可以"预处理"之后,o(1)知道每个数字左边和右边第一个比它大的位置.
②也可以o(1)知道每个数字从此位置起,往右直至其出现k次的位置在哪里.
③还可以维护每个数字,上一次出现的位置.
有了以上三个信息,可以枚举"每个位置作为第一个最大值"时,可以得到的贡献.
即合法的左区间为(max(lmx,last),i],合法的右区间为[nex,rmx). last为上一个当前数字的位置,nex第k次出现当前数字的位置.
key:其实以前做过类似的题,应该是st表写的.也是只考虑每个点,对全部右区间的贡献,而对于左区间,只考虑到上一个当前数字为止.
这样就不会算重算漏.
ps:这题的官方题解是有问题的..

int n,k;
int arr[1000006];
vector<int> vct[1000006];
vector<int> mp(1000006,0);
vector<bool> vis(1000006,false);
int last[1000006]; //上一个当前数字出现的位置.
int nex[1000006];  //下一个出现k次当数字的位置.
int lmx[1000006];  //左边第一个大于当前数字的位置.
int rmx[1000006];  //右边第一个大于当前数字的位置.
//不懂不懂..没思路...一开始想着很混乱,最大值是不同数字,又是隔开的,又是区间的,还要满足k个..晕..
//key:这个时候就要考虑,需要什么信息?可以预处理出来吗?
//①也不难..可以"预处理"之后,o(1)知道每个数字左边和右边第一个比它大的位置.
//②也可以o(1)知道每个数字从此位置起,往右直至其出现k次的位置在哪里.
//③还可以维护每个数字,上一次出现的位置.
//有了以上三个信息,可以枚举"每个位置作为第一个最大值"时,可以得到的贡献.
//即合法的左区间为(max(lmx,last),i],合法的右区间为[nex,rmx). last为上一个当前数字的位置,nex第k次出现当前数字的位置.
key:其实以前做过类似的题,应该是st表写的.也是只考虑每个点,对全部右区间的贡献,而对于左区间,只考虑到上一个当前数字为止.
这样就不会算重算漏.
//顾影自怜--这题官方题解是有问题的..
//https://codeforces.com/group/L9GOcnr1dm/contest/564037/attachments/download/28062/statements.pdf
void solve(){       //G
    cin>>n>>k;
    for(int i=1;i<=n+2;i++) vct[i].clear(),mp[i]=0,vis[i]=false,last[i]=0,nex[i]=0,lmx[i]=0,rmx[i]=0;
    for(int i=1;i<=n;i++) {
        cin>>arr[i];
        last[i]=mp[arr[i]];
        mp[arr[i]]=i;
        vct[arr[i]].emplace_back(i); //可知第k个arr[i]的位置.
    }
    if(k==1){} //最多的情况是(n+(1+n))/2,爆int...一开始没开longlong,怕MLE.然后wa2了,但是实际上完全不会MLE..也不用特判.
    stack<int> stk; //单调栈.
    for(int i=1;i<=n;i++){
        while(!stk.empty()&&arr[i]>=arr[stk.top()]) stk.pop();
        if(!stk.empty()) lmx[i]=stk.top();
        stk.emplace(i);  //这里不用判条件了,直接入栈
    }
    while(!stk.empty()) stk.pop();
    for(int i=n;i>=1;i--){
        while(!stk.empty()&&arr[i]>=arr[stk.top()]) stk.pop();
        if(!stk.empty()) rmx[i]=stk.top();
        else rmx[i]=n+1;
        stk.emplace(i); //这里不用判条件了,直接入栈
    }
    for(int i=1;i<=n;i++){
        if(vis[arr[i]]) continue;
        vis[arr[i]]=true;
        for(int j=0;j+k-1<(int)vct[arr[i]].size();j++){
            nex[vct[arr[i]][j]]=vct[arr[i]][j+k-1];
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(!nex[i]||nex[i]>rmx[i]) continue;
        int l=max(lmx[i],last[i])+1;
        int r=rmx[i]-1;
        ans+=(i-l+1)*(r-nex[i]+1);
    }
    cout<<ans<<endl;
}

原文地址：https://blog.csdn.net/qq_42643660/article/details/143579065

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：了解 .NET 运行时与 .NET 框架：基础概念与相互关系
下一篇：[数组基础] 0054. 螺旋矩阵

vue 版本升级
这个警告是说eslint-plugin-vue package支持 node 12.22或者 14.17 或者 16.0.0以上版本，但是当前你的版本是 12.19.0，版本太低了需要更新 node版
阅读更多2024-11-09
理解虚拟 DOM：Vue 的灵魂之处
虚拟 DOM（Virtual DOM）是一个轻量级的 JavaScript 对象，它是实际 DOM 的一个抽象表示。在 Vue 中，当我们对数据进行修改时，框架不会立即更新真实的 DOM，而是首先对虚
阅读更多2024-11-09
vue3 动态路由+动态组件+缓存应用
vue3 动态路由+动态组件+缓存应用
阅读更多2024-11-09
机器学习—训练细节
然后张量流会试图最小化均方误差，在这个表达式中，用大写的J(W,B)来表示成本函数，成本函数是神经网络中所有参数的函数，所以你可以把W，B看作包括整个神经网络中的所有的W，B参数，所以如果你优化关于w
阅读更多2024-11-09
解释Python中的装饰器的作用
装饰器接收两个参数：一个是要装饰的函数，另一个是可选的额外参数列表。装饰器可以返回一个新的函数，这个新函数是原始函数的增强版，或者保持和原始函数相同的行为。装饰器在Python中是一种特殊类型的函数，
阅读更多2024-11-09
我自己nodejs练手时常用的一些库基础用法
我自己使用node练手时常用的一些库的基本使用记录：有bcrypt,express,pg,config,jwt和pm2
阅读更多2024-11-09
EasyPlayer.js无插件H5播放器支持哪些浏览器？
为了确保用户无论在何种设备或浏览器上都能享受到最佳的观看体验，EasyPlayer.js流媒体播放器应运而生，它以其卓越的跨浏览器兼容性和功能丰富性，成为了视频播放解决方案的佼佼者。这种广泛的兼容性使
阅读更多2024-11-09
Java-I/O框架13：文件夹的递归遍历和递归删除
16.29 递归遍历和递归删除_哔哩哔哩_bilibili。1.文件夹的递归遍历。2.文件夹的递归删除。
阅读更多2024-11-09
github和Visual Studio
使用很简单，自己稍微琢磨下就明白了。
阅读更多2024-11-09
Python毕业设计选题：基于django+vue的网上购物系统的设计与实现
网上购物系统是在实际应用和软件工程的开发原理之上，运用Python语言以及Django框架进行开发。首先要进行需求分析，分析出网上购物系统的主要功能，然后设计了系统结构。整体设计包括系统的功能、系统总
阅读更多2024-11-09

2024 CCPC Liaoning Provincial Contest

相关文章