首页 > 其他分享 >AtCoder Beginner Contest(abc) 327

AtCoder Beginner Contest(abc) 327

时间：2023-11-05 18:56:11浏览次数：42  
标签：AtCoder abc int long st 327 tie dp define



B - A^A

难度: ⭐

题目大意

给出一个数n, 问是否存在一个数m, 使mm = n;

解题思路

因为n的数据范围很大, 到1e18, 经过打表可以发现, 当m=16时就已经大于1e18了, 因为数很多所以用了__int128, 因为double会损失精度;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 3e3 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
signed main(){
    cin >> n;
    bool f = false;
    for (int i = 1; i <= 17; i++) {
        __int128 sum = 1;
        for (int j = 1; j <= i; j++) {
            sum = sum * i;
        }
        if (sum==n) {
            cout << i;
            return 0;
        }
    }
    cout << -1;
    return 0;
}



C - Number Place

难度: ⭐

题目大意

给定一个9*9的数字表格, 检查它是否满足数独的要求, 即9个3 * 3的小九宫格中都有数字1~9, 每一行和每一列也都是1~9;

解题思路

数据不大, 暴力即可;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 3e3 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
int g[10][10];
PII a[10] = {{1,1},{1,4},{1,7},{4,1},{4,4},{4,7},{7,1},{7,4},{7,7}};
int b[10];
signed main(){
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            cin >> g[i][j];
        }
    }
    bool f = true;
    for (int i = 1; i <= 9; i++) {
        memset(b, 0, sizeof b);
        for (int j = 1; j <= 9; j++) {
            b[g[i][j]]++;
        }
        for (int i = 1; i <= 9; i++) {
            if (b[i] == 0) {
                f = false;
                break;
            }
        }
    }
    for (int j = 1; j <= 9; j++) {
        memset(b, 0, sizeof b);
        for (int i = 1; i <= 9; i++) {
            b[g[i][j]]++;
        }
        for (int i = 1; i <= 9; i++) {
            if (b[i] == 0) {
                f = false;
                break;
            }
        }
    }
    for (int k = 0; k < 9; k++) {
        memset(b, 0, sizeof b);
        int x = a[k].first, y = a[k].second;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                b[g[x + i][y + j]]++;
            }
        }
        for (int i = 1; i <= 9; i++) {
            if (b[i]==0) {
                f = false;
                break;
            }
        }
    }
    if (f) cout << "Yes";
    else cout << "No";
    return 0;
}



D - Good Tuple Problem

难度: ⭐⭐

题目大意

现在有n个人编号为1~n, 给定A1 ~ Am和B1 ~ Bm, 其中Ai和Bi是敌对的; 问最后能否把这n个人分为两个阵营, 每个阵营中没有敌对的人;

解题思路

一道比较明显的染色法判定二分图模板题, 这个就不多说了; 本题还可以用并查集来做;
我们用数组st[i]表示和i为敌对关系的人是谁, 初始情况全设为-1; 这样当我们取出一对Ai和Bi时, 如果find(Ai)和find(Bi)相等说明无法匹配; 否则的话, 如果st[Ai] = -1, 就可以直接让st[Ai]=Bi; 如果st[Ai] != -1, 就说明st[Ai]和Bi是同一阵营的, 我们就可以让p[find(st[Ai])] = find(Bi); 以上过程Bi同理;

神秘代码

// 染色法
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
int A[N], B[N];
int st[N];
vector<int> v[N];
bool bfs(int u) {
    queue<int> q;
    q.push(u);
    st[u] = 1;
    while (q.size()) {
        int t = q.front();
        q.pop();
        for (int x : v[t]) {
            if (!st[x]) {
                st[x] = 3 - st[t];
                q.push(x);
            }
            else {
                if (st[x] == st[t]) return false;
            }
        }
    }
    return true;
}
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> A[i];
    for (int i = 1; i <= m; i++) cin >> B[i];
    for (int i = 1; i <= m; i++) {
        int x = A[i], y = B[i];
        v[x].push_back(y);
        v[y].push_back(x);
    }
    bool f=true;
    for (int i = 1; i <= n; i++) {
        if (!st[i]) {
            if (!bfs(i)) {
                f = false;
                break;
            }
        }
    }
    if (f) cout << "Yes";
    else cout << "No";
    return 0;
}

//并查集
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 4e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
int A[N], B[N];
int p[N], st[N];
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) p[i] = i;
    for (int i = 1; i <= m; i++) cin >> A[i];
    for (int i = 1; i <= m; i++) cin >> B[i];
    memset(st, -1, sizeof st);
    bool f = true;
    for (int i = 1; i <= m; i++) {
        int x = A[i], y = B[i];
        int px = find(x), py = find(y);
        if (px == py) {
            f = false;
            break;
        }
        if (st[x] == -1) st[x] = y;
        else p[find(st[x])] = py;
        if (st[y] == -1)  st[y] = x;
        else p[find(st[y])] =px;
    }
    if (f) cout << "Yes";
    else cout << "No";

    return 0;
}



E - Maximize Rating

难度: ⭐⭐⭐

题目大意

给定n个数, 我们从中挑选k个数, 这k个数和相对顺序和在原来n个数中的相对顺序一致, 把这k个数记作Q1到Qk; 请问我们k该设为多少, 并且该如何挑选这k个数可以让题目给出的公式值最大;

解题思路

观察公式, 我们发现如果k固定了, 我们只需要让左边的分子越大越好, 所以从n个数中找出k个使分子最大的数; 这个过程可以用dp来做, dp[i][j]表示在前i个数中挑选k个使分子最大的数所得的分子公式的值, 通过分子的公式可以发现dp[i][k] = dp[i-1][k-1]*0.9 + f[i], 并且对于dp[i][k]我们可以将其初始化为dp[i-1][k]; 这样就得到了转移方程: dp[i][k]=max(dp[i-1][k], dp[i-1][k-1] * 0.9 + f[i]); 最后再对dp[n][k]考虑到底选择k为多少可以得到最大值;

神秘代码

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N = 5e3 + 10;
int n, m;
double dp[N][N];
double f[N];
signed main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> f[i];
    }
    dp[1][1] = f[1];
    for(int i = 1; i <= n; i++){
        for(int k = 1; k <= i; k++){
            dp[i][k]=max(dp[i-1][k], dp[i-1][k-1]*0.9 + f[i]);
        }
    }
    double x = 1;
    double maxn=-1e9;
    for(int i = 1; i <= n; i++){
        dp[n][i] = dp[n][i]/x - 1200/sqrt(i);
        maxn=max(maxn, dp[n][i]);
        x = x*0.9+1;
    }
    printf("%.20lf",maxn);
    return 0;
}



F - Apples

难度: ⭐⭐⭐⭐

标签：AtCoder,abc,int,long,st,327,tie,dp,define
From： https://www.cnblogs.com/mostimali/p/17810887.html

相关文章

  • 『AtCoder做题记录』I
    放假之后回机房第一天，后面洛谷永久封了，第一次尝试AT随便打打,先试试不知道那场比赛T1题面：InAtCodercity,therearefiveantennasstandinginastraightline.TheyarecalledAntenna\(A,B,C,D\)and\(E\)fromwesttoeast,andtheircoordinatesare\(a,b,c,......
  • abc327G
    很容易发现条件其实就是限制二分图。那么我们设\(F(n,m)\)表示\(n\)个点，\(m\)条边组成二分图的答案（非简单图）。那么答案可以发现是\(F(n,m)\cdot2^m\)，\(2^m\)出自边的端点的两种顺序。现在来计算\(F(n,m)\)。我们这里的\(m\)很大，会达到\(1e9\)的级别，这时候很难用......
  • AtCoder Beginner Contest(abc) 317
    B-MissingNo.难度:⭐题目大意给定n个数,这n个数中最小值到最大值之间缺一个数,输出这个数;解题思路数据不大,暴力即可;神秘代码#include<bits/stdc++.h>#defineintlonglong#defineIOSios::sync_with_stdio(false),cin.tie(0),cout.tie(0)#defineendl......
  • 【杂题乱写】AtCoder-ARC115
    AtCoder-ARC115_FMigration*把问题转化成在某个限制\(mid\)下求初始局面和最终局面能到达的最小代价局面，如果相等则说明可达。比较局面的方式是比较权值，如果相等按字典序比较。对每个节点\(u\)求出权值比\(u\)小或权值与\(u\)相等且编号比\(u\)小的节点中，与\(u\)......
  • HHKB Programming Contest 2023(AtCoder Beginner Contest 327) 赛后总结
    HHKBProgrammingContest2023(AtCoderBeginnerContest327)赛后总结又没来得及写题解。。。赛时A-ab查找ab和ba，只要其中一者存在就行。#include<bits/stdc++.h>usingnamespacestd;intn;strings;intmain(){cin>>n>>s;cout<<(s.find("a......
  • Japan Registry Services (JPRS) Programming Contest 2023 (AtCoder Beginner Contes
    JapanRegistryServices(JPRS)ProgrammingContest2023(AtCoderBeginnerContest324)赛后总结可悲的是：我没来得及写题解。TaskASame秒切。直接输入排一遍序再遍历即可。#include<bits/stdc++.h>usingnamespacestd;intn,a[101];intmain(){cin>>n;......
  • [ABC327G] Many Good Tuple Problems 题解
    题意对于一对长度均为\(M\)且元素值在\(\left[1,N\right]\)之间的序列\((S,T)\)，定义其为好的当且仅当：存在一个长度为\(N\)的\(01\)序列\(X\)，使得其满足如下条件：对于任意\(i\in\left[1,M\right]\)，有\(X_{S_i}\neqX_{T_i}\)。给定\(N,M\)，求在所有可......
  • ABC327 总结
    A傻逼题，降智吃了一发罚时。B依旧是傻逼题，std::pow炸精度又吃了一发罚时。C傻逼题，切了D发现就是个判断二分图，切了。E一眼丁真，感觉最后一个一定是最大的，然后就是求以最大的结尾的LIS。交上去，喜提WA29。转变思路，考虑dp。设\(f_{i,j}\)表示当前选了\(i\)个（从后往......
  • HHKB Programming Contest 2023(AtCoder Beginner Contest 327)
    HHKBProgrammingContest2023(AtCoderBeginnerContest327)A-abintmain(){IOS;strings;cin>>n>>s;boolf=false;for(inti=1;i<n;++i)if(s[i-1]=='a'&&s[i]=='b&#......
  • Atcoder Beginner Contest 327 解题报告
    AtcoderBeginnerContest327HintsD$\quad$这个定义……看起来这么熟悉？E$\quad$固定$k$试试？F_1$\quad$扫描线？F_2$\quad$区间加，区间$\max$，咋维护？A直接查找\(\texttt{ab}\)和\(\texttt{ba}\)即可。intn;strings;voidSolve(intCASE){ cin>>n>>s; pu......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99