首页 > 其他分享 >2022-2023 ACM-ICPC German Collegiate Programming Contest (GCPC 2022)

2022-2023 ACM-ICPC German Collegiate Programming Contest (GCPC 2022)

时间：2023-09-11 22:36:07浏览次数：44  
标签：std cout Contest German cin long int 2022 using

A. Alternative Architecture

img

当倾斜放置时，一定可以构成直角三角形。枚举高用勾股定理算出底，然后在利用相似三角形即可算出另一条构成的直角三角形的边长，此时判断边是否都是整数即可。

原图实际上点在格子上，一个常见的套路是边减一就可以转换成点在定点上。

#include <bits/stdc++.h>

using namespace std;

#define int long long


int32_t main() {
    int a , b , res = 1;
    cin >> a >> b , a -- , b --;
    if( a < b ) swap( a , b);
    for( int x = 1 , y ; x < a ; x ++ ){
        y = sqrt( a * a - x * x );
        if( x * x + y * y != a * a ) continue;
        if( (x * b) % a == 0 and ( y * b ) % a == 0 ) {
            res ++;
        }
    }
    if( a != b ) res *= 2;
    cout << res << "\n";
    return 0;
}

B. Breeding Bugs

枚举任意两个数，如果和为质数则在两个点之间连接一条边。这样的话，题目就转换成了求最大独立集的问题。

现在加上有三个点\(a,b,c\)满足\(a+b=p_1,b+c=p_2\)，再不考虑质数是二的情况下，\(a+c=p_1+p_2-2\times c\)。可以知道的是\(a+c\)一定是合数所以\(a,c\)之间不会连边。在考虑2的情况，可以想到的是只有\(1+1=2\)所以 1 最多只能选择一个，所以要提前把图中多余的\(1\)删掉。这样的话图中就不会出现奇环的情况，则图一定是二分图。

二分图最大独立集=点数-最大匹配点数，二分图的最大匹配用匈牙利算法求。

#include <bits/stdc++.h>

using namespace std;

const int M = 2e7+5;
bitset<M>notPrime;//不是素数

void getPrimes(){
    int n = 2e7;
    notPrime[1] = notPrime[0] = 1;
    for( int i = 2 ; i * i <= n ; i ++ ){
        if( notPrime[i] ) continue;
        for( int j = i * 2 ; j <= n ; j += i )
            notPrime[j] = 1;
    }
}

const int N = 755;

int c[N], p[N];
vector<int> e[N], vis;

void paint(int x, int z) {
    c[x] = z, vis[x] = 1;
    for (auto y: e[x]) {
        if (vis[y]) continue;
        paint(y, z ^ 1);
    }
}

bool match(int i) {
    for (auto j: e[i]) {
        if (!vis[j]) {
            vis[j] = 1;
            if (p[j] == 0 or match(p[j])) {
                p[j] = i;
                return true;
            }
        }
    }
    return false;
}

int read() {
    int x = 0, ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x;
}

int32_t main() {
    int n, vis1 = 0;
    n = read();
    vector<int> a(1);
    for (int i = 1, x; i <= n; i++) {
        x = read();
        if (x == 1) {
            if (vis1 == 0) vis1 = 1, a.push_back(1);
        } else a.push_back(x);
    }
    n = a.size() - 1;
    getPrimes();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < i; j++)
            if (notPrime[ a[i] + a[j] ] == false )
                e[i].push_back(j), e[j].push_back(i);


    vis = vector<int>(n + 1);
    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;
        paint(i, 0);
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (c[i]) continue;
        vis = vector<int>(n + 1);
        if (match(i)) ans++;
    }
    cout << n - ans << "\n";

    return 0;
}

C. Chaotic Construction

单点修改区间查询，可以使用树状数组实现。

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 256;

struct BinaryIndexedTree {
#define lowbit(x) ( x & -x )
    int n;
    vector<int> b;

    BinaryIndexedTree(int n) : n(n), b(n + 1, 0) {};

    BinaryIndexedTree(vector<int> &c) {
        n = c.size(), b = c;
        for (int i = 1, fa = i + lowbit(i); i <= n; i++, fa = i + lowbit(i))
            if (fa <= n) b[fa] += b[i];
    }

    void add(int i, int y) {
        for (; i <= n; i += lowbit(i)) b[i] += y;
        return;
    }

    int calc(int i) {
        int sum = 0;
        for (; i; i -= lowbit(i)) sum += b[i];
        return sum;
    }

    int calc(int l, int r) {
        if (l > r) return 0ll;
        return calc(r) - calc(l - 1);
    }
};

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, q, sum = 0;
    cin >> n >> q;
    BinaryIndexedTree bit(n);
    vector<int> b(n + 1);
    string op;
    for (int x, y, cnt; q; q--) {
        cin >> op;
        if (op == "-") {
            cin >> x;
            if (b[x] == 0) b[x] = 1, bit.add(x, 1), sum++;
        } else if (op == "+") {
            cin >> x;
            if (b[x] == 1) b[x] = 0, bit.add(x, -1), sum--;
        } else {
            cin >> x >> y;
            if (x > y) swap(x, y);
            cnt = bit.calc(x, y);
            if( b[x] == 1 or b[y] == 1 ) cout << "impossible\n";
            else if (cnt == 0 or cnt == sum) cout << "possible\n";
            else cout << "impossible\n";
        }
    }
    return 0;
}

其实我们这道题并不需要准确的知道两个点之间具体有多少个，所以我们也可以使用set维护当前所有的路障

#include <bits/stdc++.h>

using namespace std;

#define int long long


int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    set<int> vis;
    string op;
    for (int x, y; q; q--) {
        cin >> op;
        if (op == "+") cin >> x, vis.erase(x);
        else if (op == "-") cin >> x, vis.insert(x);
        else {
            cin >> x >> y;
            if (x > y) swap(x, y);
            if (vis.empty()) cout << "possible\n";
            else if (vis.count(x) or vis.count(y))cout << "impossible\n";
            else if (x > *vis.rbegin()) cout << "possible\n";
            else if (y < *vis.begin()) cout << "possible\n";
            else if (x < *vis.begin() and *vis.rbegin() < y) cout << "possible\n";
            else if ( *vis.lower_bound(x) > y  )cout << "possible\n";
            else cout << "impossible\n";
        }
    }
    return 0;
}

D. Diabolic Doofenshmirtz

首先不考虑\(t\)递增的条件，我们每一次询问\(t\)会得到\(x=t\mod n\)，假设\(n=4\)

\(t\) 1 2 3 4 5 6 7 8
\(x\) 1 2 3 0 1 2 3 0

这样的话发现\(x<t\)满足单调性，且满足条件\(t\)的最小值就是\(n\)，这样我们可以二分做这道题。

现在再来考虑\(t\)必须满足递增的情况，首先当\(t>x\)时\(t-x=kn\)，我们上一次询问的\(t_{last}>t\)时，可以询问\(t’\)，其中\(t'\)满足\(t_last<t’,t’=t+kn\)。为什么？因为\(t’\equiv t(\mod n)\)

这样我们就可以考虑二分做这道题。

#include <bits/stdc++.h>

using namespace std;

#define int long long


int32_t main() {
    int l = 1, r = 1e12, res = -1, kn = LLONG_MAX;
    for (int mid, lastT = -1, t, k , x ; l <= r;) {
        mid = (l + r) >> 1, t = mid;
        if (t <= lastT) {
            k = (lastT - t + kn) / kn;
            t = t + k * kn;
        }
        cout << "? " << t << endl << flush;
        lastT = t;
        cin >> x;
        if( x < mid ) res = mid , r = mid - 1 , kn = min( kn , mid - x );
        else l = mid + 1;
    }
    cout << "! "<< res << endl << flush;
    return 0;
}

还有一种考虑是倍增，从 1 开始问，每次乘 2，第一次满足\(x < t\)时，$n = t - x $

#include <bits/stdc++.h>

using namespace std;

#define int long long

int32_t main() {
    int t = 1 , x ;
    for(  ; true ; t *= 2 ){
        cout << "? " << t << endl;
        cin >> x;
        if( x < t ) break;
    }
    cout << "! " << t - x << endl;
    return 0;
}

E. Enjoyable Entree

其实可以设两种的汤的数量是 1 ，则\(f[1] = 1 , f[2] = 0, g[1]=0,g[2]=1\)。

当\(i>3\)时，有\(f[i]=f[i-1]+2\times f[i-2],g[i]=g[i-1]+2\times g[i-2]\)，同时可以发现\(f[i]=g[i-1]\)

这样的话，第\(i\)次的占比分别为\(\frac{f[i]}{f[i]+g[i]},\frac{g[i]}{f[i]+g[i]}\)

并且我们发现这个比值趋于稳定在$\frac{1}{3},\frac 2 3 $，所以当本次的比值和上一次的比值变化小于一定的阈值后可以直接输出答案。

这个阈值我设置为\(10^{-9}\)轻松通过。

#include <bits/stdc++.h>

using namespace std;

using ldb = long double;
#define int long long
constexpr ldb eps = 1e-9;


int32_t main() {
    int n;
    cin >> n;
    if (n == 1) {
        cout << "100 0\n";
        return 0;
    } else if (n == 2) {
        cout << "0 100\n";
        return 0;
    }
    ldb x = 0, y = 1, z, last = y / (x + y), now;
    for (int i = 3; i <= n; i++) {
        z = x * 2.0 + y, now = z / (y + z);
        x = y, y = z;
        if (abs(now - last) < eps) break;
        last = now;
    }
    cout << fixed << setprecision(10) << 100.0 * x / (x + y) << " " << 100.0 * y / (x + y) << "\n";
    return 0;
}

歪个题，如果不需要比值，而是准确的两个\(f[i],g[i]\)的话，这类问题我们可以矩阵快速幂解决，本题的转移矩阵如下。

\[\begin{bmatrix} 1 & 0\\ 0 & 1 \end{bmatrix} \times \begin{bmatrix} 0 & 2 \\ 1 & 1 \end{bmatrix}^{n-2} \]

H. Hardcore Hangman

首先我们先询问26个字母，这样可以得到字符串的长度。

然后我们给英文字母标号，标号可以表示成 5 位二进制数。

开一个和字符串等长度的数组。

我们第\(i\)询问，所有标号中含有\(2^i\)的字母，并给对应下标加上\(2^i\)。

从 \(i\)从 0 到 4 询问后，数组中的数就对应了字母的标号输出即可。

#include <bits/stdc++.h>

using namespace std;

#define int long long

int32_t main() {
    cout << "? ";
    for (char i = 'a'; i <= 'z'; i++) cout << i;
    cout << endl;
    int n;
    cin >> n;
    for (int i = 1, x; i <= n; i++) cin >> x;
    vector<int> a(n + 1);
    for (int i = 0, t; i < 5; i++) {
        cout << "? ";
        for (int j = 0; j < 26; j++)
            if (j & (1 << i)) cout << (char) ('a' + j);
        cout << endl;
        cin >> t;
        for (int j = 1, x; j <= t; j++)
            cin >> x, a[x] |= (1 << i);
    }
    cout << "! ";
    for (int i = 1; i <= n; i++)
        cout << (char) ('a' + a[i]);
    cout << endl;
    return 0;
}

I. Improving IT

因为题目的特殊限制\(n\cdot m < 5\times 10^5\)。所以直接\(O(nm)\)的 dp 即可。

当然还有这一种思路是建图然后跑最短路。

#include <bits/stdc++.h>

using namespace std;

#define int long long


int32_t main() {
    int n,m;cin>>n>>m;
    vector<int> w(n+2);
    vector<vector<int>>ve(n+1 , vector<int>(m+1));
    for(int i=1;i<=n;++i){
        cin>> w[i];
        for( int j = 1 ; j <= min( m , n - i + 1 ) ; j ++ )
            cin >> ve[i][j];
    }

    int  res = LLONG_MAX;
    vector<int>dp(n+5,5e14);
    dp[1] = w[1];
    for(int i=1;i<=n;++i){
        for(int j=max(1ll,i-m);j<i;++j){
            dp[i] = min( dp[i] , dp[j] + w[i] - ve[j][i-j] );
        }
        if( i + m > n )
            res = min( res , dp[i] - ve[i][n-i+1]);
    }
    cout << res << "\n";
    return 0;
}

J. Jesting Jabberwocky

首先我们可以全拍列出排列方式共 24 种。

然后 dp 求一下最小花费即可。\(f[i][j]\)表示把前\(i\)位合法，且最后一个数是\(j\)的最小代价，这里用\(j=0\)表示把前面的数字全部移动到后面。

转移的时候只需要考虑当前数字应不应该放在这里。

#include <bits/stdc++.h>

using namespace std;

vector p = {0, 1, 2, 3, 4};
constexpr int inf = 1e9;
int res = inf;

int32_t main() {
    string s;
    cin >> s;
    int n = s.size();
    vector<int> a(1);
    for (auto i: s) {
        if (i == 'h') a.push_back(1);
        else if (i == 'c') a.push_back(2);
        else if (i == 'd') a.push_back(3);
        else a.push_back(4);
    }
    do {
        vector<vector<int>> f(n + 1, vector<int>(5, inf));
        f[0][0] = 0;
        for (int i = 1, t; i <= n; i++) {
            t = p[a[i]];
            for (int j = 0; j <= 4; j++)
                if (j != t) f[i][j] = f[i - 1][j] + 1;
            for (int j = 0; j <= t; j++)
                f[i][t] = min(f[i][t], f[i - 1][j]);
        }
        res = min(res, *min_element(f[n].begin(), f[n].end()));
    } while (next_permutation(p.begin(), p.end()));
    cout << res << "\n";
    return 0;
}

K. K.O. Kids

按照题意模拟

#include <bits/stdc++.h>

using namespace std;

int32_t main() {
    int n , k , p = 0;
    string s;
    cin >> n >> k >> s;
    for( auto i : s){
        if( p == 0 and i == 'R' ) k --;
        else if( p == 1 and i == 'L' ) k --;
        else p ^= 1;
    }
    cout << max(0, k ) ;
}

L. Lots of Land

猜到的一个结论是，如果合法的话，一定存在一种情况使得所有的矩形形状相同，这样我们枚举形状，然后这个形状能不能放进去即可。

#include <bits/stdc++.h>

using namespace std;

#define int long long


int32_t main() {
    int n, m, k;
    cin >> n >> m >> k;
    if ((n * m) % k != 0) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }
    int s = n * m / k;
    for (int x = 1, y; x <= s; x++) {
        if( s % x != 0 ) continue;
        y = s / x;
        if (n % x or m % y) continue;
        for( int i = 0 , t = m / y ; i < n ; i ++ ){
            for( int j = 0 ; j < m ; j ++ ){
                cout << char( 'A' + (i / x) * t + j / y) ;
            }
            cout << "\n";
        }
        return 0;
    }
    cout << "IMPOSSIBLE\n";
    return 0;
}

标签：std,cout,Contest,German,cin,long,int,2022,using
From： https://www.cnblogs.com/PHarr/p/17694709.html

相关文章

  • 2022年9月11日
    今天下课之后，课后作业是登录界面设计，我首先用java中自带的命令框实现了功能。其中的难点就是生成一个随机的字符串当做验证码。之后我想要使用html去实现这个程序。但是在我写完html程序之后，简单的画完了一个登录框。代码如下：<!DOCTYPEhtml><html><head><title>登录界面</tit......
  • JOISC 2022 D4T2 鱼 2
    洛谷传送门LOJ传送门为了方便，设\(a_0=a_{n+1}=\infty\)。考虑拎出来所有区间\([l,r]\)使得\(\sum\limits_{i=l}^ra_i<\min(a_{l-1},a_{r+1})\)。那么\([l,r]\)中的所有鱼都不能吃到\([l,r]\)外面的鱼。那么\([1,n]\)中能吃掉所有鱼的鱼，一定不被......
  • 开源 & Dad：聊一下我与 2022 的故事
    开源&Dad：聊一下我与2022的故事董天成​github.com/andycall​关注他 22人赞同了该文章​展开目录 每个人都有这自己难忘的2022年，同样，2022对于我来说，是个重要的人生转折点。通常每次在新年的时候，我都是向前看，想象着新的一年后，自......
  • AtCoder Beginner Contest 044 C (背包DP、思维、*1583)
    C-TakandCards题意：给定$N$个正整数$x_1,x_2,\cdot\cdot\cdot,x_n$和一个正整数$A$,问从中选择$k$个数\((k>0)\),满足：这$k$个数的平均值是$A$的方案总数是多少?思路：......
  • CSP-S2022初赛易错题解析
    一.2.错误原因：不会解析：real代表实际运行时间，user代表用户态运行时间，sys表示内核态运行时间，故选A 5.错误原因：不会解析：基数排序的思路类似于桶排序，故选A 9.错误原因：不会解析：这个问题可以转化成圆排列问题，公式为A(n-1,n-1)，即(n-1)!,要考虑从两个方向看的图，所以要除......
  • [Writeup]2022 NewstarCTF_Week2(Web部分)
    一只网络安全菜鸟--(˙<>˙)/--写博客主要是想记录一下自己的学习过程，过两年毕业了也能回头看看自己都学了些啥东西。由于本人水平有限内容难免有错误、疏漏、逻辑不清、让人看不懂等各种问题，恳请大家批评指正如果我写的东西能对你有一点点帮助，那真是再好不过了......
  • 2022ICPC南京站D
    1：题意给你一个序列要求你进行一次操作，选一个位置i从他开始往后加数直到加到第i+m-1个，加的值成等差求操作完后的第k大的数2：思路1）:二分答案二分找到第k大的值2）：差分check里面，枚举每一个数看他是否大于mid，记录为num，小于的判断他是否+等差最后一位小于mid，小于直接跳过，大于则判断......
  • Codeforces Round 819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022
    给一个长为\(n\)的正整数数组，执行以下操作严格一次。选择\(l,r,(1\leql<r\leqn)\)，任意一个正整数\(k\)。重复\(k\)次：让\([l,r]\)的数组成环，按顺时针走一次。希望\(a_n-a_1\)最大，找到这个数。分类讨论题。先判断\(n\)为\(1\)时\(a_n-a_1\)......
  • 2022年线下赛的一道流量分析题
    题目给了一个where_is_password.pcapngbinwalk看到里面有个压缩包，利用foremost分离出来压缩包需要密码分析流量包，发现存在sql注入提取出来进行url解码，可以看到利用二分法进行sql盲注ascii有128个所以从>64开始判断,返回用户名或密码错误，然后判断>32,没有返回错误，说明在3......
  • 2019-2020 ACM-ICPC Brazil Subregional Programming Contest
    D.DenouncingMafia给定一颗树，然后给定\(k\)个起点，对于每个起点来说，从该点到根节点的一条链都会被染色，求最多有几个点会被染色\(3\leqn\leq1e5,1\leqk\leqn\)题解我们贪心的来看，起点一定会选择在叶子节点，假设叶子节点的数量为\(cnt\)，所以如果\(k\geqcnt\)，那么......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99