2021-12-12【Panasonic Programming Contest 2021(AtCoder Beginner Contest 231)】【题解A-G】

2021-12-12【Panasonic Programming Contest 2021(AtCoder Beginner Contest 231)】【题解A-G】 A - Water Pressure 题目大意

在 D 米深度处，以兆帕为单位的水压是多少？ code:

#include  
using namespace std;
  
int main(){
    float x,y;
    cin>>x;
    cout< 
B - Election 
题目大意 
 
找出获得最多选票的候选人的姓名。 给定的输入保证有一个获得最多选票的唯一候选人。 
code: 
#include
using namespace std;
int main(){
	int n;
	cin>>n;
	mapa;
	for(int i=0;i>s;
		a[s]++;
	}
	string ans;
	int mx=0;
	for(auto i:a)
	{
		int cnt=i.second;
		if(cnt>mx)
		{
			ans=i.first;
			mx=cnt;
		}
	}
	cout< 
C - Counting 2 
题目大意 
 
N 个学生中有多少人的身高至少为 x 
coed： 
#include 
using namespace std;
int main() {
    long long n,q;
    cin >> n >> q;
    vector a(n);
    vector vecq(q);
    for(auto &v : a) {cin >> v;}
    for(auto &v : vecq) {cin >> v;}
    sort(a.begin(),a.end()); 
    for (long long i=0;i 
D - Neighbors 
题目大意 
 
确定是否有办法将编号为 1 到 N 的 N 人并排排成一行，以满足以下格式中的所有 M 个条件。条件：
    
     
      
       
        
         A
        
        
         i
        
       
      
      
       A_i
      
     
    Ai​和
    
     
      
       
        
         B
        
        
         i
        
       
      
      
       B_i
      
     
    Bi​是相邻的。 
code: 
#include
#include

#define fi first
#define se second
#define eb emplace_back

using namespace std;
using namespace atcoder;
using ll = long long;

int main() {
    int N, M; cin >> N >> M;
    vector cnt(N); 
    dsu d(N); //并查集
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a; --b;
        ++cnt[a];
        ++cnt[b];
        if (cnt[a] > 2 || cnt[b] > 2 || d.same(a, b)) {
            cout << "No" << endl;
            return 0;
        }
        d.merge(a, b);
    }
    cout << "Yes" << endl;
    return 0;
}
 
#include
using namespace std;

int n,m,tot=0,qwq=0; 
int f[1000005];
int pre[1000005];//并查集

int Find(int x){
	if(pre[x]!=x) pre[x]=Find(pre[x]);
	return pre[x]; 
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) pre[i]=i;//初始化
	for(int i=1,x,y;i<=m;i++){
		scanf("%d%d",&x,&y);
		int fx=Find(x),fy=Find(y);
		if(fx==fy) return printf("No"),0;
		pre[fx]=fy;
		f[x]++,f[y]++;
	}
	for(int i=1;i<=n;i++){
		if(f[i]>2) return printf("No"),0;
	} 
	 printf("Yes");
	return 0;
}
 
E - Minimal payments 
题目大意 
 
仅使用这些硬币支付价值 X 日元的产品时，用于付款并作为找零退回的硬币的最少总数是多少？
 
准确地说，当 Y 是至少为 X 的整数时，求精确表示 Y 日元所需的硬币数量和精确表示 Y-X 日元所需的硬币数量的最小总和。
 
code: 
#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;
 
 
int n;
vector a;
map,ll> mp;
 
ll solve(ll x, int k) {
    if (mp.find({x,k}) != mp.end()) return mp[{x,k}];
    cerr << x << " " << k << endl;
    if (k == n-1) return mp[{x,k}] = x;
    ll b = a[k+1]/a[k];
    return mp[{x,k}] = min(solve(x/b,k+1)+x%b,solve(x/b+1,k+1)+b-x%b);
}
 
int main() {
    ll x;cin >> n >> x;
    a.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    cout << solve(x,0) << endl;
    return 0;
}
 
#include
using namespace std;
typedef long long ll;
const ll inf = 1e18 + 10;
const int maxl = 105;
 
ll x;
ll c[maxl], n, a[maxl], d[maxl];
ll f[maxl][2];
 
int main() {
    cin >> n >> x;
    for (int i = n; i >= 1; i--) {
        cin >> a[i];
    }
 
    for (int i = 1; i <= n; i++) {
        d[i] = x / a[i];
        x %= a[i];
    }
 
    for (int i = 1; i <= n; i++) {
        if (i == 1) {
            f[i][0] = d[i];
            f[i][1] = d[i] + 1;
        } else {
            ll k = a[i-1] / a[i];
            f[i][0] = d[i] + f[i-1][0];
            f[i][0] = min(f[i][0], k - d[i] + f[i-1][1]);
 
            f[i][1] = d[i] + 1 + f[i-1][0];
            f[i][1] = min(f[i][1], k - d[i] - 1 + f[i-1][1]);
        }
    }
    cout << f[n][0] << endl;
 
    return 0;
}
 
F - Jealous Two 
题目大意 
 
Snuke 计划给高桥和青木各送一件礼物。
 礼物有 N 个候选人。 高桥对第 i 个候选人的印象是 
    
     
      
       
        
         A
        
        
         i
        
       
      
      
       A_i
      
     
    Ai​ ，青木对第 i 个候选人的印象是 
    
     
      
       
        
         B
        
        
         i
        
       
      
      
       B_i
      
     
    Bi​
 
两人非常嫉妒。 如果高桥对青木收到的礼物的印象大于高桥对高桥收到的礼物的印象，高桥就会嫉妒青木并开始打架，反之亦然。
 
在 
    
     
      
       
        
         N
        
        
         2
        
       
      
      
       N^2
      
     
    N2 种可能的送礼方式中，有多少不会导致战斗？
 
code: 
#include
#define SZ 200005
using namespace std;
typedef long long ll;
typedef pair pii;
 
int tree[SZ];
 
void add(int pos, int val) {
    ++pos;
    while (pos < SZ) {
        tree[pos] += val;
        pos += (pos&-pos);
    }
}
 
int sum(int pos) {
    ++pos;
    int ret = 0;
    while (pos > 0) {
        ret += tree[pos];
        pos &= (pos-1);
    }
    return ret;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector v(N);
    for (auto& e : v) {
        cin >> e.first;
    }
    vector coor;
    for (auto& e : v) {
        int x;
        cin >> x;
        e.second = x;
        coor.push_back(x);
    }
    sort(coor.begin(),coor.end());
    for (auto& e : v) {
        e.second = coor.begin()-lower_bound(coor.begin(), coor.end(), e.second);
    }
    sort(v.begin(), v.end());
    long long ans = N;
    int prev = -100;
    int prevx = -100;
    int accu = 1;
    for (auto& e : v) {
        int a = e.first;
        int x = -e.second;
        if (a == prev && x == prevx) {
            ans += sum(SZ-1)-sum(x-1) + accu;
            accu++;
        } else {
            accu = 1;
            ans += sum(SZ-1)-sum(x-1);
        }
        add(x,1);
        prev = a;
        prevx = x;
    }
    cout << ans << 'n';
    return 0;
}
 
G - Balls in Boxes 
题目大意 
 
code: 
#include 
using namespace std;
const long long MOD=998244353;
long long dp[1001];
long long f(long long x, long long n){
    if(n==0) return 1LL;
    if(n&1) return x*f(x,n-1)%MOD;
    long long h=f(x,n/2);
    return h*h%MOD;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long k;
    cin >> n >> k;
    vector v(n);
    for(int i=0;i> v[i];
    dp[0]=1;
    for(int i=0;i0;j--) dp[j]=(dp[j]+dp[j-1]*v[i])%MOD;
    }
    long long invn=f(n,MOD-2);
    long long ans=1;
    for(int i=0;i					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5657700.html