A - Water Pressure
题目大意
在 D 米深度处，以兆帕为单位的水压是多少？
code:
#include <bits/stdc++.h>
using namespace std;
int main(){
float x,y;
cin>>x;
cout<<x/100<<endl;
return 0;
}
B - Election
题目大意
找出获得最多选票的候选人的姓名。 给定的输入保证有一个获得最多选票的唯一候选人。
code:
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
map<string,int>a;
for(int i=0;i<n;i++)
{
string s;
cin>>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<<ans<<endl;
}
C - Counting 2
题目大意
N 个学生中有多少人的身高至少为 x
coed：
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n,q;
cin >> n >> q;
vector<long long> a(n);
vector<long long> 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<q;i++) {
cout << a.end() - lower_bound(a.begin(), a.end(), vecq[i]) << endl;
}
}
D - Neighbors
题目大意
确定是否有办法将编号为 1 到 N 的 N 人并排排成一行，以满足以下格式中的所有 M 个条件。条件： A i A_i Ai和 B i B_i Bi是相邻的。
code:
#include<bits/stdc++.h>
#include<atcoder/all>
#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<int> 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<bits/stdc++.h>
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<ll> a;
map<pair<ll,int>,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<bits/stdc++.h>
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<bits/stdc++.h>
#define SZ 200005
using namespace std;
typedef long long ll;
typedef pair<int, int> 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<pii> v(N);
for (auto& e : v) {
cin >> e.first;
}
vector<int> 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 <bits/stdc++.h>
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<long long> v(n);
for(int i=0;i<n;i++) cin >> v[i];
dp[0]=1;
for(int i=0;i<n;i++){
for(int j=n;j>0;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<n;i++) ans=(ans*v[i])%MOD;
long long cur=1;
for(int i=1;i<=n;i++){
cur=cur*(k+1-i)%MOD*invn%MOD;
if(cur==0) break;
ans=(ans+cur*dp[n-i])%MOD;
}
cout << ans;
}
京公网安备 11010502036488号