沈陽資格賽賽后補題

C - Play with bombs

思路：可以二分列舉最久的時間，然后判斷一下每個炸彈的爆炸時間和這個最久的時間相差多少，如果炸彈爆炸的時間比列舉的時間大，就不用管，因為它到最后肯定也不會爆炸，如果比列舉的時間小的話，就要記錄它們的差值，最后對所有炸彈累加的差值和列舉的最久時間進行判斷（列舉的最久時間其實就是能進行多少輪，也就是能給炸彈加多少次1），

注意會爆int，
————————————————
著作權宣告：本文為CSDN博主「Than-」的原創文章，遵循CC 4.0 BY-SA著作權協議，轉載請附上原文出處鏈接及本宣告，
原文鏈接：https://blog.csdn.net/weixin_44137005/article/details/109447322

#include <bits/stdc++.h>
using namespace std;
#define jiechufengyin std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
const int maxn = 1e5 + 10;
const int minn = 1e3 + 10;
#define mod 1000000007

int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}

int lcm(int a, int b){
    return a * b / gcd(a, b);
}

ll ksm(ll a, ll b){
    ll ans = 1;
    while (b){
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

int a[maxn];
int Case = 1, t, n;

int check(ll x){
    ll sum = 0;
    for (int i = 1; i <= n; i++){
        if (a[i] < x)
            sum += (x - a[i]);
    }
    if (sum <= x)
        return 1;
    else
        return 0;
}

int main(){
    jiechufengyin;
    cin >> t;
    while (t--){
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        ll l = 0, r = 2*(ll)inf;
        while (l <= r){
            ll mid = (l + r) / 2;
            if (check(mid))
                l = mid + 1;
            else
                r = mid - 1;
        }
        printf("Case #%d: %lld\n", Case++, l);
    }
    return 0;
}

I - Clarke and MST

最大生成樹，最小生成樹選最小的邊換成選最大的邊即可，
但是注意題目是說用位運算&實作，

#include <bits/stdc++.h>
using namespace std;
typedef long ll;
const int N = 3e5 + 7;
const int M = 3e5 + 7;
#define jiechufengyin std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

struct point{
    int x;
	int y;
    int w;
}p[M];

int t;
int n,m, ans;
int f[N];

void init(){
    for(int i = 0; i < n + 1; i++){
        f[i] = i;
    }
}

int findfather(int v){
	if(f[v] == v) return v;
	else{
		f[v] = findfather(f[v]);
		return f[v];
	}
}

bool cmp(point a, point b){
    return a.w > b.w;
}

bool flag;
int num;

void merge(int u, int v, int x){
	int t1, t2;
	t1 = findfather(u);
	t2 = findfather(v);
	if(t1 != t2){
        if(flag){
            ans = p[x].w;
            flag = 0;
        }
		else{
            ans &= p[x].w;
        }
        f[t1]=t2;
            num--;
    }
    return ;
}

int main(){
	jiechufengyin;
    cin >> t;
    while(t--){
        cin >> n >> m;
        init();
        for(int i = 0; i < m; i++){
            cin >> p[i].x >> p[i].y >> p[i].w;
        }
        sort(p, p + m, cmp);
        flag = 1;
        num = n-1;
        for(int i = 0; i < m; i++){
            merge(p[i].x, p[i].y, i);
        }
        if(num!=0){
            cout << '0' << endl;
        }
        else{
            cout << ans << endl;
        }
    }
    return 0;
}

J - Let’s go hiking

隊友A的

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
using namespace std;
typedef long long ll;
int dp[105][105];
struct yyqxwyb
{
	int x,y;
	int v;
};
yyqxwyb zz[10050];
int a[105][105];
bool cmp(yyqxwyb a1,yyqxwyb a2)
{
	if(a1.v!=a2.v)return  a1.v<a2.v;
	else if(a1.x!=a2.x)return a1.x<a2.x;
	else return a1.y<a2.y;
}
int main()
{
	int r,c;
	cin>>r>>c;
	int f=1;
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<=c;j++)
		{
			cin>>a[i][j];
			zz[f].v=a[i][j];
			zz[f].x=i;
			zz[f].y=j;
			f++;
		}
	}
	sort(zz+1,zz+f,cmp);
	//dp[zz[1].x][zz[1].y]=1;
	for(int i=1;i<=r*c;i++)
	{
		int bz=a[zz[i].x][zz[i].y];
		if(a[zz[i].x+1][zz[i].y]<bz)dp[zz[i].x][zz[i].y]=max(dp[zz[i].x][zz[i].y],dp[zz[i].x+1][zz[i].y]);
		if(a[zz[i].x-1][zz[i].y]<bz)dp[zz[i].x][zz[i].y]=max(dp[zz[i].x][zz[i].y],dp[zz[i].x-1][zz[i].y]);
		if(a[zz[i].x][zz[i].y+1]<bz)dp[zz[i].x][zz[i].y]=max(dp[zz[i].x][zz[i].y],dp[zz[i].x][zz[i].y+1]);
		if(a[zz[i].x][zz[i].y-1]<bz)dp[zz[i].x][zz[i].y]=max(dp[zz[i].x][zz[i].y],dp[zz[i].x][zz[i].y-1]);
		dp[zz[i].x][zz[i].y]+=1;
	}
	
	int maxx=0;
	for(int i=1;i<=r*c;i++)
	{
		maxx=max(maxx,dp[zz[i].x][zz[i].y]);
	}
	cout<<maxx<<'\n';
	return 0;
}

M - Sum of 2050

水題，但是要注意都要開ll，會爆int

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll t;
ll n, ans;

ll qiuweishu(ll x)
{
	ll sum = 0;
	while(x)
	{
		sum += (x % 10);
		x /= 10;
	} 
	return sum;
}


int main()
{
	cin >> t;
	for (int i = 1; i <= t; ++i)
	{
		cin >> n;
		ans = 0;
		ll temp;
		if(n % 2050 == 0){
			temp = n / 2050;
			ans = qiuweishu(temp);
			cout << ans << endl;
			continue;
		} 
		else cout << "-1" << endl;
	}
	
	return 0;
}