首页 > 其他分享 >2024 暑假友谊赛 2

2024 暑假友谊赛 2

时间：2024-07-20 20:22:13浏览次数：15  
标签：ve int cin 2024 ++ vector solve 暑假 友谊赛

A

题目链接

思路：

枚举每个十字中心点，合法就标记，最后若还剩下点没被标记就NO

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define PII pair<int, int>
const int N = 1e6 + 5, mod = 998244353, Mod = 1e9 + 7;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

void solve() {
    int n;
    cin >> n;
    vector<string> ve(n);
    for (int i = 0; i < n; ++i) cin >> ve[i];
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (ve[i][j] == '.') {
                bool ok = true;
                for (int k = 0; k < 4; ++k) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x < 0 || x >= n || y < 0 || y >= n || ve[x][y] != '.') {
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    ve[i][j] = '#';
                    for (int k = 0; k < 4; ++k) {
                        int x = i + dx[k], y = j + dy[k];
                        ve[x][y] = '#';
                    }
                }
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (ve[i][j] != '#') {
                cout << "NO";
                return ;
            }
        }
    }
    cout << "YES";
}


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

    return 0;
}

B

题目链接

思路：

首先是看样例就可以找出一些构造的方法

求按位与的话可以把所有数的二进制表示出来，由于是按位与，有一位为0的话就一直为0，考虑到这一点，可以构造一个大的数‘让代码误以为那是大的数’，类似100000，只有首位是1，后面全是0，在后续只需要用011111将首位的1消掉，那么这个数就变成了最小的数

构造方法如下（k为二进制数，其他数的二进制位数为k的二进制位数+1）：

11111     k   00000

10000   11111  011111 

 

void solve() {
    int k;
    cin >> k;
    int cnt = 0;
    int x = k;
    while (x) {
        cnt ++;
        x /= 2;
    }
    if (k == 0) cnt = 1;
    cout << 2 << ' ' << 3 << '\n';
    cout << (int)(pow(2, cnt + 1) - 1) << ' ' << k << ' ' << 0 << '\n';
    cout << (int)(pow(2, cnt)) << ' ' << (int)(pow(2, cnt + 1) - 1) << ' ' << (int)(pow(2, cnt) - 1);
}

C

题目链接

思路：

可以把网格看成黑白相间的棋盘格，只要同一颜色的都在白色或都在黑色格子上就不会冲突

假设就先用1填充黑格，用2填充白格，那么一定有一方会先填完，最后剩下的那方有两种选择，根据给的x来选择即可

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define PII pair<int, int>
const int N = 1e6 + 5, mod = 998244353, Mod = 1e9 + 7, inf = 1e18;



void solve() {
    int n;
    cin >> n;
    vector<vector<int> > ve(n + 1, vector<int> (n + 1));
    vector<PII> a[3];
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i % 2) {
                if (j % 2) a[1].push_back({i, j});
                else a[2].push_back({i, j});
            } else {
                if (j % 2) a[2].push_back({i, j});
                else a[1].push_back({i, j});
            }
        }
    }
    int op;
    int col1, col2;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            int x;
            cin >> x;
            if (a[1].size() && a[2].size()) {
                if (x != 1) {
                    cout << 1 << ' ';
                    cout << a[1].back().first << ' ' << a[1].back().second << '\n';
                    cout << '\n';
                    a[1].pop_back();
                } else {
                    cout << 2 << ' ';
                    cout << a[2].back().first << ' ' << a[2].back().second << '\n';
                    cout << '\n';
                    a[2].pop_back();
                }
                if (a[1].empty()) op = 2, col1 = 2, col2 = 3;
                if (a[2].empty()) op = 1, col1 = 1, col2 = 3;
            } else {
                if (x != col1) {
                    cout << col1 << ' ' << a[op].back().first << ' ' << a[op].back().second << '\n';
                    cout << '\n';
                    a[op].pop_back();
                } else {
                    cout << col2 << ' ' << a[op].back().first << ' ' << a[op].back().second << '\n';
                    cout << '\n';
                    a[op].pop_back();
                }
            }
        }
    }
}

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

    return 0;
}

D

题目链接

思路:

要满足字典序最小，那得让更小的字符在前面，考虑用双指针

从最小的字符x开始处理，从后开始找，找到后再从前开始找第一个大于x的字符，那么就可以将它们交换，同时更新边界，这两个字符外的字符不能在变

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int L = 0, R = n - 1;
    for (int i = 0; i < 26; ++i) {
        if (L >= R) break;
        char y = i + 'a';
        int l = L;
        for (int j = R; j > l; --j) {
            if (s[j] == y) {
                while (l < j && s[l] <= y) {
                    l ++;
                }
                if (l < j && s[l] > y) {
                    swap(s[l], s[j]);
                    L = l + 1, R = j - 1;
                    l ++;
                }
            }
        }
    }
    cout << s;
}

E

题目链接

思路：

统计每个数的增量，若更改全局的值就情况所有增量，输出的时候全局加上该数的增量即可

 

void solve() {
    int n;
    cin >> n;
    map<int, int> mp;
    int now = 0;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        mp[i] = x;
    }
    int q;
    cin >> q;
    while (q --) {
        int op;
        cin >> op;
        if (op == 1) {
            if (mp.size()) mp.clear();
            int x;
            cin >> x;
            now = x;
        } else if (op == 2) {
            int x, y;
            cin >> x >> y;
            mp[x] += y;
        } else {
            int x;
            cin >> x;
            int ans = now;
            if (mp.count(x)) ans += mp[x];
            cout << ans << '\n';
        }
    }
}

F

题目链接

思路：将a和b按a排个序，对于当前的ai选择b1到bi中任意个数使得和为ai，直接用背包dp维护即可

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define PII pair<int, int>
const int N = 5e3 + 5, mod = 998244353, Mod = 1e9 + 7, inf = 1e18;

struct E {
    int a, b;
};

void solve() {
    int n;
    cin >> n;
    vector<E> ve(n);
    int ma = 0;
    for (int i = 0; i < n; ++i) {
        cin >> ve[i].a;
        ma = max(ma, ve[i].a);
    }
    for (int i = 0; i < n; ++i) {
        cin >> ve[i].b;
    }
    int ans = 0;
    auto cmp = [](E x, E y) {
        return x.a < y.a;
    };
    sort(ve.begin(), ve.end(), cmp);
    vector<int> f(N);
    f[0] = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= ve[i].a - ve[i].b; ++j) {
            ans = (ans + f[j]) % mod;
        }
        for (int j = ma; j >= ve[i].b; -- j) {
            f[j] = (f[j] + f[j - ve[i].b]) % mod;
        }
    }
    cout << ans;
}

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

    return 0;
}

H

题目链接

思路：

若S集里的点的父亲节点都属于同一条路径，那么就满足条件

可以用dfs序来判断，可以知道子树的dfs序范围，将S集的父亲节点按dfs序排序后，可以往深处依次判断是否在同一条链上

 

也可以用LCA来做，找出S集中最深的点x，S中其余点到与x的LCA的距离一定不能大于1，由此判断是否都满足

dfs序：

#include <bits/stdc++.h>

using namespace std;

//#define int long long
#define PII pair<int, int>
const int N = 1e6 + 5, mod = 998244353, Mod = 1e9 + 7;

vector<int> f, L, R, g;
vector<vector<int> > ve;
void solve() {
    int n, m;
    cin >> n >> m;
    ve = vector<vector<int> > (n + 1);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        ve[u].push_back(v), ve[v].push_back(u);
    }
    f = L = R = g = vector<int>(n + 1);
    int idx = 0;
    auto dfs = [&] (int u, int fa, auto dfs) -> void {
        f[u] = fa;
        L[u] = idx ++;
        for (auto v:ve[u]) {
            if (v == fa) continue;
            dfs (v, u, dfs);
        }
        R[u] = idx ++;
    };
    dfs(1, 1, dfs);
    auto cmp = [=] (int a, int b) {
        return L[a] < L[b];
    };

    for (int u = 1; u <= m; ++u){
        int k;
        cin >> k;
        for (int i = 0; i < k; ++i) {
            cin >> g[i];
            g[i] = f[g[i]];
        }
        sort(g.begin(), g.begin() + k, cmp);
        int l = 0, r = idx;
        bool ok = true;
        for (int i = 0; i < k; ++i) {
            if (L[g[i]] >= l && R[g[i]] <= r) {
                l = L[g[i]], r = R[g[i]];
            } else {
                ok = false;
                break;
            }
        }
        if (ok) cout << "YES\n";
        else cout << "NO\n";
    }
}

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

    return 0;
}

lca：

#include <bits/stdc++.h>

using namespace std;

//#define int long long
#define PII pair<int, int>
const int N = 1e6 + 5, mod = 998244353, Mod = 1e9 + 7;

vector<int>g[N];//图
vector<int>dep(N);//深度
vector<vector<int>>f(N,vector<int>(20+5));//f[i][j]表示从i向祖先走2^j步

void dfs(int u){
    for(int i=0;i<g[u].size(); ++i){
        int to=g[u][i];
        if(dep[to])continue;
        f[to][0]=u;
        dep[to]= dep[u] + 1;
        for(int j=1;j<=20;++j)f[to][j]=f[f[to][j-1]][j-1];
        dfs(to);
    }
}

int lca(int a,int b){//求a和b的最近公共祖先
    if(dep[a]<dep[b])swap(a,b);
    for(int i=20;i>=0;--i)
        if(dep[f[a][i]]>=dep[b])a=f[a][i];
    if(a==b){//a走到b
        return a;
    }

    //a和b到同一层后，一起向祖先走
    for(int i=20;i>=0;--i){
        if(f[a][i]!=f[b][i]){
            a=f[a][i],b=f[b][i];
        }
    }
    return f[a][0];
}

void init(){
    dep[1]=1;//根为1
    dfs(1);
}

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }
    init();
    for (int u = 1; u <= m; ++u){
        int k;
        cin >> k;
        vector<int> ve(k);
        int ma = -1, x;
        for (int i = 0; i < k; ++i) {
            cin >> ve[i];
            if (dep[ve[i]] > ma) {
                ma = dep[ve[i]];
                x = ve[i];
            }
        }
        bool ok = true;
        for (int i = 0; i < k; ++i) {
            int fa = lca(x, ve[i]);
            if (dep[ve[i]] - dep[fa] > 1) {
                ok = false;
                break;
            }
        }
        if (ok) cout << "YES\n";
        else cout << "NO\n";

    }
}

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

    return 0;
}

I

题录链接

思路：

dp，考虑走到[i][j]的最少操作和当前钱数

若不需要最少操作则可以一直操作某个p[i][j]直到可以走到[n][n]，所以考虑怎么样换p[i][j]能够减少次数

假设[i][j]走到[k][l]都是操作p[i][j]换的钱，若p[k][l]>p[i][j]那么操作p[k][l]换钱的次数会比操作p[i][j]换钱的次数少，则可以考虑换成操作p[k][l]来换钱

转换的同时，还需要走的到[k][l]，所以先n2预处理出[i][j]走到[l][k]的最小距离，求出走到[k][l]需要的操作p[i][j]最少多少次，更新走到[k][l]时最少操作数和当前钱数

所以总的复杂度是n4的

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define PII pair<int, int>
const int N = 1e6 + 5, mod = 998244353, Mod = 1e9 + 7, inf = 1e18;



void solve() {
    int n;
    cin >> n;
    vector<vector<int> > p, r, d;
    p = r = d = vector<vector<int> > (n + 1, vector<int> (n + 1));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) cin >> p[i][j];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j < n; ++j) cin >> r[i][j];
    for (int i = 1; i < n; ++i)
        for (int j = 1; j <= n; ++j) cin >> d[i][j];
    vector<vector<array<int, 2> > > f(n + 1, vector<array<int, 2> > (n + 1, {inf, 0}));
    f[1][1] = {0, 0};
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            vector<vector<int> > dis(n + 1, vector<int> (n + 1, inf));
            dis[i][j] = 0;
            for (int k = i; k <= n; ++k) {
                for (int l = j; l <= n; ++l) {
                    dis[k][l] = min({dis[k][l], dis[k - 1][l] + d[k - 1][l], dis[k][l - 1] + r[k][l - 1]});
                }
            }
            auto [cnt, now] = f[i][j];
            for (int k = i; k <= n; ++k) {
                for (int l = j; l <= n; ++l) {
                    if (k != n || l != n) {
                        if (p[k][l] < p[i][j]) continue;
                    }
                    auto [cnt, now] = f[i][j];
                    int cost = max(0ll, (dis[k][l] - now + p[i][j] - 1) / p[i][j]);
                    int now1 = now + cost * p[i][j] - dis[k][l];
                    int cnt1 = cnt + cost + k - i + l - j;
                    if (cnt1 < f[k][l][0] || (cnt1 == f[k][l][0] && now1 > f[k][l][1]))
                        f[k][l] = {cnt1, now1};
                }

            }
        }
    }
    cout << f[n][n][0];
}

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

    return 0;
}

G

题目链接

思路：

首先满足条件的3个点可以再构成一个点

（x1, y1） （x1, y2）
（x2, y1） （x2, y2）

可以将x和y拎出来看，x1——y1，x2——y1，x1——y2，且构成了（x2， y2）

可以看成y1和x1、x2有关系，而x1和y1、y2有关系，并且构成后x2和y2也有了关系

就可以看成x和y维护并查集，点（xi，yi）说明xi和yi有关系，在同一个集合里的x和y都可以构成点

所以最后求的就是连通块的个数

当一个点都没有的时候，需要再加n + m - 1个点（手动数下也行啦，（x1，y1~ym）(x2~xn，y)）

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define PII pair<int, int>
const int N = 4e5 + 5, mod = 998244353, Mod = 1e9 + 7, inf = 1e18;

int fa[N];
int find(int x) {
    if (x != fa[x]) fa[x] = find(fa[x]);
    return fa[x];
}
void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i <= n + m; ++i) fa[i] = i;
    int ans = n + m - 1;
    for (int i = 0; i < q; ++i) {
        int x, y;
        cin >> x >> y;
        y += n;
        x = find(x), y = find(y);
        if (x != y) fa[x] = y, ans --;
    }
    cout << ans;
}

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

    return 0;
}

 

标签：ve,int,cin,2024,++,vector,solve,暑假,友谊赛
From： https://www.cnblogs.com/bible-/p/18313031

相关文章

  • $NOI2024$游记
    day-?~day-?考了期末考后打省队集训，刚开始打的很差，bai了几天状态恢复。打进前4了，好吃捏。$day-1$报道日，育才宿舍真难泵，真独立卫浴，全是蚊子受不了，想不通育才学生一间住八个人怎么活下去的（。育才辣椒不辣，开心！没洗澡，不嘻嘻。day0今年竟是NOI四十周年，dzd英雄人物上位救赎ccf（bu......
  • 暑假第三周总结(7.15-7.20)
    这周做了什么继续学习JAVA,做出了城堡游戏点击查看代码//RoompackagecastleV3;importjava.util.HashMap;publicclassRoom{ privateStringdescription;privateHashMap<String,Room>exits=newHashMap<String,Room>();publicRoom(String......
  • 2024“钉耙编程”中国大学生算法设计超级联赛（1）结题报告1 2 8
    1001循环位移字符串哈希将a展开*2对于每个长度为len_a的序列进行一次hash存储并将其插入set中对于b进行一次哈希对于每个长度为len_a的连续子串进行一次查询点击查看代码#include<bits/stdc++.h>usingnamespacestd;//22222constintN=5e6+10;constintp1......
  • 暑假集训CSP提高模拟3
    暑假集训CSP提高模拟3\(T1\)P117.abc猜想\(100pts\)原题:[ARC111A]SimpleMath2由题，有\(\dfrac{(a^{b}-a^{b}\bmodc)\bmodc^{2}}{c}\)即为所求。证明设\(\left\lfloor\dfrac{a^{b}}{c}\right\rfloor=\dfrac{a^{b}-a^{b}\bmodc}{c}=kc+r\)，其中\(r......
  • 2024牛客暑期多校训练营2 解题报告
    B-MST对于整个序列进行一次kruskal对于序列中如果需要访问的点数小于300那么将所有的点的边存入序列中进行kruskal如果大于300那么直接对于所有的点进行kruskal点击查看代码#include<bits/stdc++.h>#defineintlonglong#defineall(x)x.begin(),x.end()#defineral......
  • 国开大学2024《企业法律实务（省开课）》
    5.当事人互负债务，没有先后履行顺序的，应当（）A.同时履行B.法院判决C.去法院起诉D.申请仲裁答案：A6.商务谈判法律实务是指企业法务人员在民商事谈判活动中运用（）知识，按照商业规则，促成商业交易成就或阻止商业交易成就的行为活动。A.法律   B.商业C.专业D.谈判答案：A7.根据......
  • 2024年IDEA&IntelliJ系列最新激活码(2088)！
    蛋疼ing，仅供学习使用。K384HW36OB-eyJsaWNlbnNlSWQiOiJLMzg0SFczNk9CIiwibGljZW5zZWVOYW1lIjoibWFvIHplZG9uZyIsImxpY2Vuc2VlVHlwZSI6IlBFUlNPTkFMIiwiYXNzaWduZWVOYW1lIjoiIiwiYXNzaWduZWVFbWFpbCI6IiIsImxpY2Vuc2VSZXN0cmljdGlvbiI6IiIsImNoZWNrQ29uY3VycmVudFVzZSI6ZmFsc2U......
  • 2024年 Intellij IDEA | idea&IDEA系列激活码（持续更新）
       声明：仅供学习使用：K384HW36OB-eyJsaWNlbnNlSWQiOiJLMzg0SFczNk9CIiwibGljZW5zZWVOYW1lIjoibWFvIHplZG9uZyIsImxpY2Vuc2VlVHlwZSI6IlBFUlNPTkFMIiwiYXNzaWduZWVOYW1lIjoiIiwiYXNzaWduZWVFbWFpbCI6IiIsImxpY2Vuc2VSZXN0cmljdGlvbiI6IiIsImNoZWNrQ29uY3VycmVudFVzZSI6ZmFsc......
  • 2024年Intellij IDEA&& idea系列激活码（持续更新）
    声明：仅供学习使用声明：仅供学习使用：K384HW36OB-eyJsaWNlbnNlSWQiOiJLMzg0SFczNk9CIiwibGljZW5zZWVOYW1lIjoibWFvIHplZG9uZyIsImxpY2Vuc2VlVHlwZSI6IlBFUlNPTkFMIiwiYXNzaWduZWVOYW1lIjoiIiwiYXNzaWduZWVFbWFpbCI6IiIsImxpY2Vuc2VSZXN0cmljdGlvbiI6IiIsImNoZWNrQ29uY3VycmVudF......
  • NOID2024 游记
    流水账。Day-13中考7.2考完，7.4就被gj叫过来集训了。和同学讨论了一下，发现自己语文作文很可能会偏题，很可能考不上JellyFish中学。Day-12背笔试，比较简单，很快就背完了。mx这几天每天都有模拟赛，比较累。Day-6丢失了一场模拟赛。中午去吃饭去晚了，被迫吃屎。Day-4......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99