首页 > 其他分享 >3.11-3.17

3.11-3.17

时间：2024-03-12 22:33:54浏览次数：25  
标签：10 int 3.11 3.17 vis vector mp res

天梯赛选拔第二场：

L2-1：队列模拟

void solve() {
    int n,k;
    cin >> n >> k;
    stack<int> q,box;
    for(int i=1;i<=n;i++) {
        int x;
        cin >> x;
        q.push(x);
    }
    stack<int> res;
    vector<int> ans;
    while(q.size() || box.size()) {
        if(q.size()) {
            int x = q.top();
            q.pop();
            if(res.empty()) res.push(x);
            else {
                int y = res.top();
                if(x>y && x-y<=k) res.push(x);
                else {
                    if(box.size()) {
                        int t = box.top();
                        if(t>y && t-y<=k) {
                            res.push(t);
                            box.pop();
                        }
                    }
                    box.push(x);
                }
            }
        }
        if(q.empty()) {
            q = box;
            while(box.size()) box.pop();
            if(res.size()==1) { 
                int t = res.top();
                res.pop();
                ans.push_back(t);
            }
            else {
                while(res.size()) cout << res.top() << ' ' , res.pop();
                cout << endl;
            }
        }
    }
    for(auto & t : ans) cout << t << ' ';
}
View Code

 

L2-3：n有1e5大小。所以对于每一个数字，预处理每一个点长度和各个位数之和。然后对于每一个 x ，令总和为 w ，枚举前i位之和，去找满足条件的abs(w-x)的个数。

PII get(int x) {
    PII res;
    while(x) {
        res.first++;
        res.second+=x%10;
        x/=10;
    }
    return res;
}

vector<int> get_(int x) {
    vector<int> v;
    while(x) v.push_back(x%10) ,x/=10;
    reverse(v.begin() , v.end());
    return v;
}

void solve() {
    int n;
    cin >> n;
    map<int , int> mp;
    map<int , int> len,sum,mp1,mp2,mp3,mp4;
    for(int i=1;i<=n;i++) {
        int w;
        cin >> w;
        mp[w]++;
        PII x = get(w);
        len[w]=x.first , sum[w]=x.second;
        if(x.first&1 && x.second&1) mp1[x.second]++;
        else if(x.first&1 && x.second%2==0) mp2[x.second]++;
        else if(x.first%2==0 && x.second&1) mp3[x.second]++;
        else mp4[x.second]++;
    }
    int ans=0;
    for(auto & [s,b] : mp) {
        int x = 0 , y = sum[s] , res=0;
        vector<int> v;
        v = get_(s);
        for(int j=0;j<v.size();j++) {
            x += v[j] , y -= v[j];
//            cout << x << ' ' << y << endl;
            int z = abs(x-y);
//            cout << z << endl;
            if(len[s]&1) {
                if(sum[s]&1) res+=mp1[z];
                else res+=mp2[z];
            }
            else {
                if(sum[s]&1) res+=mp3[z];
                else res+=mp4[z];
            }
        }
//        cout << "res: " << res << endl;
        ans+=res*b;
//        cout << ans << endl << endl;
    }
    cout << ans << endl;
}
View Code

 

L2-4：优先队列小顶堆处理每一个节点，直到不能取为止。

void solve() {
    int n,m,x,y,t;
    cin >> n >> m >> x >> y >> t;
    vector<vector<int>> v(n+10,vector<int>(m+10));
    vector<vector<int>> f(n+10,vector<int>(m+10));
    vector<vector<bool>> vis(n+10,vector<bool>(m+10));
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            cin >> v[i][j] , f[i][j]=v[i][j];
        }
    }
    while(t--) {
        int a,b;
        cin >> a >> b;
        f[a][b]=-1;
    }
    f[x][y]=-1;
    priority_queue<PII , vector<PII> , greater<PII>> q;
    q.push({f[x][y],{x,y}});
    int power=0;
    while(q.size()) {
        int w = q.top().first , xt = q.top().second.first , yt = q.top().second.second;
        q.pop();
        if(vis[xt][yt]) continue;
        vis[xt][yt]=1;
        if(power >= w) {
            power += v[xt][yt];
            for(int i=1;i<=4;i++) {
                int xx = xt + dx[i];
                int yy = yt + dy[i];
                if(xx>=1 && xx<=n && yy>=1 && yy<=m && !vis[xx][yy]) {
                    q.push({f[xx][yy],{xx,yy}});
                }
            }
        }
    }
    cout << power << endl;
}
View Code

 

L3-1：dp：令 f[n][k] 表示前n个数选k组得到的最大和。对于每组是是那个节点到哪个节点，只要

f[n][k]-f[n-m][k-1] == vis[n]-vis[n-m] 即表示这一段被选择。

void solve() {
    int n,m,k;
    cin >> n >> m >> k;
    vector<int> v(n+10),vis(n+10);
    vector<vector<int>> f(n+10,vector<int>(k+10));
    for(int i=1;i<=n;i++) cin >> v[i] , vis[i]=vis[i-1]+v[i];
    for(int i=m;i<=n;i++) {
        for(int j=1;j<=k;j++) {
            f[i][j]=max(f[i-1][j],f[i-m][j-1]+vis[i]-vis[i-m]);
        }
    }
//    for(int i=1;i<=n;i++) {
//        for(int j=1;j<=k;j++) cout << f[i][j] << " \n"[j==k];
//    }
    vector<pair<int , int>> ans;
    int i = n , j = k;
    while(k) {
        if(f[i][k]-f[i-m][k-1]==vis[i]-vis[i-m]) {
            ans.push_back({i-m+1,i});
            i=i-m;
            k--;
        }
        else i--;
    }
    cout << f[n][j] << endl;
    reverse(ans.begin() , ans.end());
    for(auto & [a,b] : ans) cout << a << ' ' << b << endl;
}
View Code

 

L3-2：对于一棵树，每次有两种操作，要么使某个节点值加 x ；要么求某一个节点形成的子树的价值是多少。

dfs序哈希一下每个节点，然后树状数组维护前缀和即可。

//　／l、
//（ﾟ､ 。 ７
//　l、 ~ヽ
//　じしf_, )ノ
//  不要放弃！猫猫会为你加油！
#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

const int N = 5e5+10 , M = 1e6+10 ;

int n,m,cnt;
int tr[N],dis[N];
vector<int> v[N];
map<int , int> mp;

int lowbit(int x) {
    return x & -x;
}

void add(int x,int d) {
    for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=d;
}

int query(int x) {
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}

int dfs(int x) {
    mp[x]=++cnt;
    dis[mp[x]]=1;
    for(auto & t : v[x]) {
        dis[mp[x]]+=dfs(t);
    }
    return dis[mp[x]];
}

void solve() {
    cin >> n >> m;
    vector<int> w(n+10);
    for(int i=1;i<=n;i++) cin >> w[i];
    for(int i=2;i<=n;i++) {
        int x;
        cin >> x;
        v[x].push_back(i);
    }
    dfs(1);
//    for(int i=1;i<=n;i++) cout << i << ' ' << mp[i] << ' ' << dis[mp[i]] << endl;
    for(int i=1;i<=n;i++) add(mp[i],w[i]);
//    for(int i=1;i<=n;i++) cout << query(mp[i]) - query(mp[i]-1) << endl;
    while(m--) {
        int op;
        cin >> op;
        if(op&1) {
            int x,y;
            cin >> x >> y;
            add(mp[x],y);
        }
        else {
            int x;
            cin >> x;
            cout << query(mp[x]+dis[mp[x]]-1) - query(mp[x]-1) << endl;
        }
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    int T = 1;
//    cin >> T ;
    while(T--) solve();
    return 0;
}
View Code

 

L3-3：求 i^j 的总和。

1 <= i <= n , 1 <= j <= n , 1 <= n <= 1e18。

从二进制角度来看，其实就是每一位 0 的数量乘以 1 的数量在乘以当前 2 的 i 次方即可。(要开__int28)

//　／l、
//（ﾟ､ 。 ７
//　l、 ~ヽ
//　じしf_, )ノ
//  不要放弃！猫猫会为你加油！
#include <bits/stdc++.h>
#define endl '\n'
#define int __int128

using namespace std;

const int N = 2e5+10 , M = 1e6+10 , mod = 998244353;

void solve() {
    long long n;
    cin >> n;
    int ans=0;
    for(int i=60;i>=0;i--) {
        int d = (1ll<<i) , w=d-1;
        if(n<=w) continue;
        int s = n-w;
        int a = s/(d*2ll)*d , b = a;
        if(s % (d*2ll)) {
            int y = s % (d*2ll);
            if(y<d) a+=y;
            else a+=d , y-=d , b+=y;
        }
        b+=w;
        ans = (ans + a % mod * b % mod * d % mod * 2ll % mod) % mod;
    }
    cout << (long long)ans << endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    long long T = 1;
    cin >> T ;
    while(T--) solve();
    return 0;
}
View Code

 

 

SMU 2024 spring 天梯赛1：

7-11：龙龙送外卖

有一棵树，树根是外卖店，节点上有些地方有人点外卖，问：每当有人点外卖之后，龙龙把外卖送给所有人至少需要走多少步，每两个节点之间的距离是1。

解：画一下图可以发现，龙龙所走的最短距离就是所有被覆盖的点的距离*2-离外卖店最远的那个节点。dfs处理一下正序每个节点离外卖店的距离。倒序往回标记有哪些节点被走过。记录一下最远节点的距离输出即可。

void dfs(int x,int w) {
    dis[x]=w;
    for(auto & t : ve[x]) {
        dfs(t,w+1);
    }
}

void DFS(int x) {
    vis[x]=1 , cnt++;
    for(auto & t : v[x]) {
        if(!vis[t]) DFS(t);
    }
}

void solve() {
    int root;
    cin >> n >> m;
    for(int i=1;i<=n;i++) {
        int x;
        cin >> x;
        if(x==-1) root=i;
        else {
            v[i].push_back(x);
            ve[x].push_back(i);
        }
    }
    vis[root]=1;
    dfs(root,0);
    int res=0;
    while(m--) {
        int x;
        cin >> x;
        if(!vis[x]) DFS(x);
        res=max(res,dis[x]);
        cout << cnt*2-res << endl;
    }
}
View Code

 

7-12：智能护理中心统计

也是和黄金树影一样的，dfs序加树状数组处理即可。

int n,m,cnt=0,idx=0;
vector<int> v[N];
unordered_map<string , int> mp;
int tr[N],dis[N],ru[N],hx[N];
unordered_map<int , string> lao;
bool vis[N];

int lowbit(int x) {
    return x & -x;
}

void add(int x,int d) {
    for(int i=x;i<=cnt;i+=lowbit(i)) tr[i]+=d;
}

int query(int x) {
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}

int dfs(int x) {
    vis[x]=1;
    hx[x]=++idx;
    dis[hx[x]]=1;
    for(auto & t : v[x]) {
        if(!vis[t]) dis[hx[x]]+=dfs(t);
    }
    return dis[hx[x]];
}

void solve() {
    cin >> n >> m;
    vector<pair<int , string>> res;
    for(int i=1;i<=m;i++) {
        string A,B;
        cin >> A >> B;
        if(A[0]>='A') {
            if(!mp.count(A)) mp[A]=++cnt;
            if(!mp.count(B)) mp[B]=++cnt;
            int a = mp[A] , b = mp[B];
            v[b].push_back(a);
            ru[a]++;
        }
        else {
            int d=0;
            for(int j=0;j<A.size();j++) d = d*10 + A[j]-'0';
            res.push_back({d,B});
            if(!mp.count(B)) mp[B]=++cnt;
        }
    }
    for(auto & t : mp) {
        if(!ru[t.second]) dfs(mp[t.first]);
    }
    for(auto & [x,s] : res) {
        add(hx[mp[s]],1);
        lao[x]=s;
    }
    char op;
    while(cin >> op && op!='E') {
        if(op=='Q') {
            string s;
            cin >> s;
            cout << query(hx[mp[s]]+dis[hx[mp[s]]]-1) - query(hx[mp[s]]-1) << endl;
        }
        else {
            int x;
            string s;
            cin >> x >> s;
            if(lao.count(x)) {
                string w = lao[x];
                add(hx[mp[w]],-1);
                add(hx[mp[s]],1);
            }
            else {
                add(hx[mp[s]],1);
            }
            lao[x]=s;
        }
    }
}
View Code

 

标签：10,int,3.11,3.17,vis,vector,mp,res
From： https://www.cnblogs.com/lzywakaka/p/18069513

相关文章

  • 2024.3.11 软工日报
    今天学习了安卓开发连接数据库的内容，学习时间2小时代码量150  packagecom.example.myapplication;importjava.sql.Connection;importjava.sql.DriverManager;importjava.sql.ResultSet;publicclassmysqlhelp{publicstaticintgetUserSize(){......
  • cmd 的图论练习题（近期总结 2024.3.11）
    AGC010ERearranginglink题意：一个序列\(a_{1...n}\)，两个人游戏。先手打乱这个序列，然后后手可以多次选择一对相邻的互质的数交换。先手希望最终序列字典序尽量小，后手则相反。两人都绝顶聪明，求最终序列。\(1\len\le2000,\space1\lea_i\le10^8\)考虑不互质的两个数\(a_i,a......
  • 软甲工程日报3.11
    DBpackagecom.example.myapplication;importandroid.annotation.SuppressLint;importandroid.content.ContentValues;importandroid.content.Context;importandroid.database.Cursor;importandroid.database.sqlite.SQLiteDatabase;importandroid.database.sqlite.SQ......
  • 3.11
    今天是学习开发Androidstudio 的第一天  随说明天就要验收接入数据库什么玩意的 视图层次：由View和ViewGroup组成。在创建UI时，开发人员不会真正去创建View或者ViewGroup，而是直接使用Android所提供的具有不同功能的控件，因此通常是看不到View或ViewGroup。View是Android......
  • 3.11每日总结
    净现值计算 #include<iostream>#include<iomanip>#include<cmath>constintPROJECTS=6;constintYEARS=4;intmain(){//创建二维数组储存每个项目每年利润intmoney[PROJECTS][YEARS]={{-100000,-1000000,-100000,-120000},{10000,......
  • 3.11
    今天实现通过安卓连接web后端最后在mysql数据库添加数据库的操作在安卓项目中首先在AndroidMainfest.xml中添加链接网络权限，同时允许安卓明文传输所要连接的IP地址<?xmlversion="1.0"encoding="utf-8"?><manifestxmlns:android="http://schemas.android.com/apk/res/andro......
  • 软件工程日报5 2024.03.11
     第一天第二天第三天第四天第五天所花时间（包括上课）6小时5小时4小时4小时 六小时代码量（行）300350200300 50博客量（篇）1111 1所学知识了解安卓相关数据库的知识，下载安装了matlab学习了相关安卓的布局展示了解activity之间的相互跳转以注册了......
  • 3.8~3.11闲话
    3.8因为教师资格证考试所以放假......
  • 鲜花 3.11
    这是一篇鲜花。我认为鲜花是相当好的，因为可以乐乐乐。最近精神状态一直不大好，连续n天没有写题了，鉴定为不打隔膜导致的/cf/cf/cf上周把WA2coda推完了，可能还有一个后日谈，这周回去推。怎么还有巨大的任务计划，破防了。看到hanghang的鲜花，感觉神秘敬酒环节有点可怕的，还好我......
  • anaconda环境下：强化学习PPO算法仿真环境库sample-factory的python完美适配版本为pytho
    anaconda环境下：强化学习PPO算法仿真环境库sample-factory的python完美适配版本为python3.11库sample-factory地址：https://github.com/alex-petrenko/sample-factory文档地址：https://samplefactory.dev/经过对多个版本的python进行测试，anaconda环境下只有python3.11......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99