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

AtCoder Beginner Contest(abc) 300

时间:2023-06-19 18:35:37浏览次数:52  
标签:AtCoder typedef abc f6 idx PII 300 long int




A - N-choice question

题目大意

从n个数里面找出a+b的结果

解题思路

签到题不多嗦了

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 310;
int n;
signed main() {
    int a, b;
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (x == a + b)  cout << i;
    }
    return 0;
}




B - Same Map in the RPG World

题目大意

给定两个矩阵a和b, 现在可以对b进行两种操作: 一是把矩阵的行向上移一行, 即由1 2 3 4变成2 3 4 1; 二是把矩阵的列向左移一列; 问是否能通过有限次操作让两个矩阵相同;

解题思路

因为行和列的数量都小于30; 所有直接暴力即可;

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 35;
char a[N][N];
char b[N][N];
int n,m;
bool check( int y, int z) {
    bool f = true;
    for (int i=1,j = y; i<=n; i++,j++) {
        if (j > n) j = 1;
        for (int k = z, h = 1; h<=m; k++, h++) {
            if (k > m) k = 1;
            if (a[i][h] != b[j][k]) {
                f = false;
                break;
            }
        }
        if (!f) break;
    }
    if (f) return true;
    else return false;
}
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> b[i][j];
        }
    }
    char s = a[1][1];
    for (int j = 1; j <= n; j++) {
        for (int k = 1; k <= m; k++) {
            if (b[j][k] == s) {
                if (check( j, k)) {
                    cout << "Yes";
                    return 0;
                }
            }
        }
    }
    cout << "No";
    return 0;
}




C - Cross

题目大意

给定一个只有'#'和'.'组成的矩阵, 问由'#'组成的X形状的各种大小的都有多少个

解题思路

数量不大, 直接暴力

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
char g[N][N];
int dx[] = { 1,1,-1,-1 }, dy[] = { 1,-1,1,-1 };
int n,m;
map<int, int> mp;
void check(int x, int y) {
    bool f = true;
    int idx = 0;
    while (1) {
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i]*(idx+1), b = y + dy[i]*(idx+1);
            if (a<1 || a>n || b<1 || b>m||g[a][b] != '#') {
                f = false;
                break;
            }
        }
        if (!f) break;
        idx++;
    }
    mp[idx]++;
}
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> g[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (g[i][j] == '#') {
                check(i, j);
            }
        }
    }
    int num = min(n, m);
    for (int i = 1; i <= num; i++) {
        cout << mp[i] << ' ';
    }
    return 0;
}




D - AABCC

题目大意

现在有三个质数a,b,c;(a<b<c) 现在定义一个数为a * a * b * c * c; 给定一个数n, 问不超过n的数里存在多少个这样的数

解题思路

先用线性筛出质数, 然后还是暴力...不过要注意每选一个数都要判定一次, 要不然会tle
注意这里有个坑, 因为n最大为1e12, 所以我们可以只找1e6以内的质数; 但是如果a,b,c都是1e6的数量级, 结果还是会爆long long, c会变成负数也被判定为小于n, 使答案错误; 对于我们在选a和b时, 筛选条件不能只是a* a和a* a* b, 而应该是a* a* a* a* a和a* a* b* b* b, 这样可以有效防止上述情况;

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6+10;
int n,num=0;
bool st[N];
int p[N];
void ini() {
    for (int i = 2; i <= N; i++) {
        if (!st[i]) p[num++] = i;
        for (int j = 0; p[j] * i <= N; j++) {
            st[i * p[j]] = true;
            if (i % p[j]==0) break;
        }
    }
}
signed main() {
    cin >> n;
    int idx = 0;
    ini();
    for (int i = 0; i < num - 2; i++) {
        int maxn = 0;
        int a = p[i] * p[i] * p[i] * p[i] * p[i];
        if (a > n) break;
        for (int j = i + 1; j < num - 1; j++) {
            int b = p[i] * p[i] * p[j] * p[j] * p[j];
            if (b > n) break;
            for (int k = j + 1; k < num; k++) {
                int c = p[k] * p[k] * p[j] * p[i] * p[i];
                if (c <= n) {
                    idx++;
                }
                else break;
            }
        }
    }
    cout << idx;
    return 0;
}




E - Dice Product 3

题目大意

给定一个数m初始值为1, 现有一个骰子, 可以等可能地得到1~6之间的一个数; 然后用m乘这个数来更新m; 现在给定一个数n, 只要m小于n就可以一直进行这个操作, 问m恰好可以等于n的概率为多少, 结果对998244353取模;

解题思路

这个是真不会; 一开始样例都看不明白...题解用的是记忆化搜索(这块我是真不熟...)
我先解释一下样例, 样例中n=6; 我们可以先想到如果想得到6, 那么一定是由6的因数得来的, 比如1 2 3 6; 我们设f6为当前m为6的概率, 则 f6 = ( f1+ f2+ f3+ f6) / 6;把f6移项得到 f6 = ( f1+ f2+ f3) / 5; 同理 f2 = f1/5, f3 = f1/5; 这样就得到 f6 = 7/25 * f1; 因为m初识为1, 所以f1就是1; 故f6 = 7/25; 因为239578645 * 25 ≡ 7 (mod 998244353) 故答案为239578645; 因为5对998244353的逆元为598946612, 所以我们在过程中把除以5变成乘5的逆元即可直接得到答案;
关于什么时候用记忆化搜索, 我感觉是当我们的递推过程中频繁出现之前求过的数, 那我们可以把之前求过的数都存起来, 用的时候直接取出来即可; (因为记忆化搜索地过程朴素地简直不像是一个算法, 所以一直都没怎么思考过它...)

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int mod = 998244353;
map<int, int> mp;
int n;
int idx= 598946612;
int check(int x) {
    int res=0;
    if (mp[x]) return mp[x];
    for (int i = 2; i <= 6; i++) {
        if (x % i == 0)  res= (res+check(x/i))%mod;
    }
    mp[x] = res * idx % mod;
    return  mp[x];
}
signed main() {
    mp[1] = 1;
    cin >> n;
    cout<<check(n);
    return 0;
}




F - More Holidays

题目大意

待定.....

解题思路

待定....

神秘代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=1e6+10;
int w[N],d[N];
int n,m,idx;
bool st[N];
vector<int> v[N];
int dijkstra(){
    memset(d,0x3f,sizeof d);
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    heap.push({0,1});
    d[1]=0;
    while(heap.size()){
        auto t=heap.top();
        heap.pop();
        int x=t.second;
        if(st[x]) continue;
        st[x]=true;
        for(int p:v[x]){
            if(d[p]>d[x]+w[p]){
                d[p]=d[x]+w[p];
                heap.push({d[p],p});
            }
        }
    }
    if(d[m]==0x3f3f3f3f) return -1;
    else return d[m]-1;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int k;
        cin>>k;
        w[i+m] =1;
        for(int j=1;j<=k;j++){
            int x;
            cin>>x;
            v[x].push_back(i+m);
            v[i+m].push_back(x);
        }
    }
    cout<<dijkstra();
    return 0;
}

标签:AtCoder,typedef,abc,f6,idx,PII,300,long,int
From: https://www.cnblogs.com/mostimali/p/17489133.html

相关文章

  • 从3000ms到25ms!看看人家的接口优化技巧,确实很优雅!!
    批处理避免多次IO异步处理空间换时间使用缓存预处理预计算池化思想数据库连接池,线程池。避免重复创建与销毁。优化程序结构程序经过多次迭代,多人维护开发情况下,会出现一些重复操作等等。串行改并行索引加索引,排除索引失效场景避免大事务......
  • AtCoder Regular Contest 162
    A答案即后缀最小值个数。时间复杂度\(\mathcal{O}(n)\)。提交记录:Submission#42717665-AtCoderRegularContest162B发现操作不改变逆序对个数奇偶性。逆序对个数为奇数则无解;为偶数则可以直接模拟。时间复杂度\(\mathcal{O}(n^2)\)。提交记录:Submission#42718848......
  • ABC306G 与 CF1835D 的思考
    两道题似乎都涉及了一个经典模型:在一张有向图上,给定起点\(s\)和终点\(t\),询问\(s\)到\(t\)与\(t\)到\(s\)是否均存在一条长度\(=L\)的路径(\(L\)是一个\(\gen^3\)的数)。首先\(s\)与\(t\)必须在同一个SCC内(考场上没看到互相可达直接以为不可做)。考虑取......
  • [ABC282Ex] Min + Sum
    [ABC282Ex]Min+Sum一道分治题。比较新的地方在于,别的题都是按中点为M分治,而这道题是按最小值为M分治。记录b的前缀和sum。【L,R】最小值为M,则分为【L,M-1】,【M+1,R】。 #include<bits/stdc++.h>usingnamespacestd;constintN=4e5+66;typedeflonglongll;constll......
  • AtCoder Beginner Contest 220 H Security Camera
    洛谷传送门AtCoder传送门看到数据范围猜复杂度是\(O(\text{poly}(n)2^{\frac{n}{2}})\),所以考虑折半。至少有一个端点被选不好算,考虑转成两个端点都被选,但是边数奇偶性与\(m\)相同。称编号\(<\frac{n}{2}\)的点为左点,编号\(\ge\frac{n}{2}\)的点为右点(点编号从\(0......
  • AtCoder Beginner Contest 306 题解 A - E
    A-Echo题目大意给定一个字符串,需要把它每个字符重复输出。解题思路可以读完整个字符串,也可以按照字符读一个输出两个。ACCode#include<iostream>#include<algorithm>#include<cstring>#include<numeric>#defineendl'\n'#defineiosios::sync_with_stdio(fals......
  • 题解:【ABC168F】 . (Single Dot)
    题目链接挺套路的题。如果值域和线段数量同阶,可以预处理不能越过的线段,使用状压四个方向记录每个节点能不能往这个方向走,然后直接爆搜就好了,标记上能走到哪些地方。但这个值域一看就是没有救的,于是就要拿出来离散化了。把线段的横纵坐标都拎出来离散化,依然是同样的预处理,然后从离......
  • AtCoder ABC306 DEF
    D-PoisonousFull-Course(DP)题意现在有\(N\)道菜,高桥需要依次享用。第\(i\)道菜有两个属性\((X_i,Y_i)\),其意义是:若\(X_i=0\),则第\(i\)道菜是解毒的,其美味度为\(Y_i\);若\(X_i=1\),则第\(i\)道菜是有毒的,其美味度为\(Y_i\)。当高桥享用一道菜,他的状态变化如下:......
  • AtCoder Beginner Contest 306 G Return to 1
    洛谷传送门AtCoder传送门考虑若干个能被\(1\)到达且能到达\(1\)的环,设它们的环长分别为\(a_1,a_2,...,a_k\)。那么我们现在要每个环走若干遍,使得步数不含除\(2\)或\(5\)以外的质因子。设第\(i\)个环走\(x_i\)遍,那么其实就是要求\(\sum\limits_{i=1}^ka_i......
  • How to AK ABC306
    HowtoAKABC306A题意:吧字符串的每个字符连续输出两遍,记得不要快读,不要忘记输入$n$纪念QinzhA题WA掉B题意:给定长度为$64$的数组$A$,输出$\sum_{i=0}^{63}A_i2^i$暴力模拟即可注意要开unsignedlonglong纪念我WA了$2$次,第一次用的int,第二次......