比赛地址
Dashboard - Codeforces Round 925 (Div. 3) - Codeforces
A. Recovering a Small String
直接模拟
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define lowbit(x) (x&(-x))
#define sz(a) (int)a.size()
#define pb push_back
#define all(a) a.begin(), a.end()
#define int long long
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;using namespace std;inline void solve(){int n ; cin >> n ;// a a z ; 28// a z z : 1 + 26 + 26 = 53if(n<=28){char c = (char)(n-3+'a') ;cout << "aa" <<c << endl; }else if(n<=53){char c = (char)(n-28+'a');cout << "a" << c << "z" << endl;}else{char c = (char)(n-53+'a');cout << c << "zz" << endl;}return ;
}signed main()
{IOSint _ = 1;cin >> _;while(_ --) solve();return 0;
}
B . Make Equal
模拟 , 从后往前遍历,t表示平均值 , 用 x 记录当前每个小于平均值的差 , 如果遇到一个值出现a[i]>t && a[i]-t>x,那么表示a[i]是不可能变成t的,后面需要的少于它多出来的;
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define lowbit(x) (x&(-x))
#define sz(a) (int)a.size()
#define pb push_back
#define all(a) a.begin(), a.end()
#define int long long
typedef long long LL;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;using namespace std;inline void solve() {int n ; cin >> n ;LL s = 0 ;vector<int> a(n+1) ;for(int i=1;i<=n;i++) {cin >> a[i] ;s += a[i] ;}LL t = s / n ;LL x = 0 ;bool tag = true ;for(int i=n;i>=1;i--){if(a[i] < t){x += t - a[i] ;}else{if(a[i]-t > x){tag = false;break;}x -= a[i] - t;}}if(tag) cout << "Yes" << endl;else cout << "No" << endl;}signed main()
{IOSint _ = 1;cin >> _;while (_--) solve();return 0;
}
C. Make Equal Again
模拟
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define lowbit(x) (x&(-x))
#define sz(a) (int)a.size()
#define pb push_back
#define all(a) a.begin(), a.end()
#define int long long
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;using namespace std;inline void solve(){int n ; cin >> n ;vector<int> a(n+1);for(int i=1;i<=n;i++){cin >> a[i] ;}int i=1,j=n;int ans = 0 ;if(a[i]!=a[j]){while(i<=n&&a[i]==a[1]) i++;while(j>=1 && a[j]==a[n]) j--;ans = n - max(i-1,n-j);}else{while(i<=n && a[i]==a[1]) i++;while(j>=1 && a[j]==a[1]) j--;if(j<i) ans = 0 ;else ans = j - i + 1 ;}cout << ans << endl;
}signed main()
{IOSint _ = 1;cin >> _;while(_ --) solve();return 0;
}
D. Divisible Pairs
哈希表解决!
对于( a + b ) % x = 0 , 那么a % x + b % x = 0 ;
对于(a - b)% y = 0 , 那么a % y == b % y ;
如果知道上面的,那么这道题就很简单了 ;
用哈希表来存对应的pair<int,int>,表示 : {a[i]%x,a[i]%y} ;
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define lowbit(x) (x&(-x))
#define sz(a) (int)a.size()
#define pb push_back
#define all(a) a.begin(), a.end()
#define int long long
#define PII pair<int,int>
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;using namespace std;int a[N] ;inline void solve(){int n , x , y ;cin >> n >> x >> y ;for(int i=1;i<=n;i++) cin >> a[i] ;int ans = 0 ;map<PII,int> mp;for(int i=1;i<=n;i++){// 求 x - a[i] % x 和 a[i ]% y 组成的pair前面有多少个 auto it = mp.find({(x-a[i]%x)%x,a[i]%y});if(it!=mp.end()){ans += it->second;}mp[{a[i]%x,a[i]%y}]++;} cout << ans << endl;
}signed main()
{IOSint _ = 1;cin >> _;while(_ --) solve();return 0;
}
E. Anna and the Valentine's Day Gift
贪心模拟题 ;
首先要清楚 : Anan选 后导0 最多的数消除后导0 , 然后Shasha是保护后导0最多的数 ;
遍历每一个元素,将后导0个数不为0的个数存起来,然后排序,然后每次最优都是减小最多的,减去那一部分,最后和m判断即可 ;
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define lowbit(x) (x&(-x))
#define sz(a) (int)a.size()
#define pb push_back
#define all(a) a.begin(), a.end()
#define int long long
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;using namespace std;int a[N] ;bool cmp(int x ,int y){return x > y ;
}inline void solve(){// Anan选后导0最多的数消除后导0,然后Shasha是保护后导0最多的数int n , m ; cin >> n >> m ;LL cnt = 0 ;vector<int> b ;for(int i=1;i<=n;i++){int x ; cin >> x ;int zero = 0 ;while(x%10==0){zero++;x /= 10 ;}while(x){cnt ++;x /= 10 ;}if(zero) b.push_back(zero);}sort(b.begin(),b.end(),cmp);for(int i=1;i<b.size();i+=2){cnt += b[i];}if(cnt > m) cout << "Sasha" << endl;else cout << "Anna" << endl ;return ;
}signed main()
{IOSint _ = 1;cin >> _;while(_ --) solve();return 0;
}