A - Water Pressure
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
printf("%.6lf\n" , n / 100.0 );
return 0;
}
B - Election
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false) , cin.tie(nullptr) , cout.tie(nullptr);
int n;
cin >> n;
map<string,int> cnt;
for( string s ; n ; n -- )
cin >> s , cnt[s] ++;
int ans = 0;
string res;
for( auto [k,v] : cnt )
if( v > ans ) ans = v , res = k;
cout << res ;
return 0;
}
C - Counting 2
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false) , cin.tie(nullptr) , cout.tie(nullptr);
int n , q;
cin >> n >> q;
vector<int> a(n);
for( auto & i : a ) cin >> i;
sort( a.begin() , a.end() );
for( int x ; q ; q -- ){
cin >> x;
cout << n - (lower_bound( a.begin() , a.end() , x ) - a.begin()) << "\n";
}
return 0;
}
D - Neighbors
要求是一条链,首先每个人最多只能与两个人相邻,并且不能出现成环的情况。
首先统计度数,然后跑一个拓扑序即可。
#include<bits/stdc++.h>
using namespace std;
int read() {
int x = 0, f = 1, ch = getchar();
while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
if (ch == '-') f = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x * f;
}
const int N = 1e5+5;
bool vis[N];
vector<int> e[N] ;
int d[N];
int main() {
int n = read() , m = read() , cnt = 0;
for(int u , v ; m ; m -- )
u = read() , v = read() , e[u].push_back(v) , e[v].push_back(u) ,d[v] ++ , d[u] ++;
queue<int> q;
for( int i = 1 ; i <= n ; i ++ )
if( e[i].size() > 2 ) cout << "No\n" , exit(0);
else if( e[i].size() <= 1 ) q.push(i);
while( !q.empty() ){
int u = q.front();
cnt ++ , q.pop();
for( auto v : e[u] )
if( --d[v] == 1 ) q.push(v);
}
if( cnt == n ) cout <<"Yes\n";
else cout << "No\n";
return 0;
}
E - Minimal payments
设\(f[n][x]\)表示前\(n\)种货币表示\(x\)所用的最少数目。
因为\(a_i|a_{i+1}\)恒成立,所以如果要用\(a_n\)就一定要尽可能的多用才是最优解所以$f[n-1][x\mod a_n] + \left \lfloor \frac{x}{a_n} \right \rfloor $
还有一种情况就是找零此时就是\(f[n-1][x-x\mod a_n] + \left \lceil \frac{x}{a_n} \right \rceil\)
两种取最小值即可,这样 dp 的话比较难写,所以可以采用记忆化搜索的形式。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 60+5;
int a[N];
map<int,int> f[N];
int calc( int n , int x ){
if( n == 1 ) return x;
if( f[n].find(x) != f[n].end() ) return f[n][x];
f[n][x] = calc( n-1 , x % a[n] ) + x / a[n];
if( x % a[n] ) f[n][x] = min( f[n][x] , calc( n-1 , a[n] - x % a[n] ) + x / a[n] + 1 );
return f[n][x];
}
int32_t main() {
int n , x;
cin >> n >> x;
for( int i = 1 ; i <= n ; i ++ ) cin >> a[i];
cout << calc( n , x );
}
F - Jealous Two
给第一个人的礼物是\(x\),第二个人的礼物是\(y\),要求保证\(A_x\ge A_y \and B_y \ge B_x\)
首先我们可以把礼物按照\(A_i\)排序,然后用求逆序对的方式求一下有多少\(y\)满足\(y<x\and By \ge B_x\)
值得注意的是\(A_x=A_y\and B_x=B_y\)的情况下,我们只统计了\(x>y\)的没有统计\(x<y\),解决方法就是用map
统计每种物品出现的次数,然后组合数计算一下就好。
注意\(B_i\)范围很大,需要离散化。
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
typedef long long ll;
int read() {
int x = 0, f = 1, ch = getchar();
while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
if (ch == '-') f = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x * f;
}
struct BinaryIndexedTree {
#define lowbit(x) ( x & -x )
int n;
vector<int> b;
BinaryIndexedTree(int n) : n(n), b(n + 1, 0) {};
BinaryIndexedTree(vector<int> &c) { // 注意数组下标必须从 1 开始
n = c.size(), b = c;
for (int i = 1, fa = i + lowbit(i); i <= n; i++, fa = i + lowbit(i))
if (fa <= n) b[fa] += b[i];
}
void add(int i, int y) {
for (; i <= n; i += lowbit(i)) b[i] += y;
return;
}
int calc(int i) {
int sum = 0;
for (; i; i -= lowbit(i)) sum += b[i];
return sum;
}
};
int32_t main() {
int n = read();
vector<pii> p(n);
vector<int> t;
for (auto &[a, b]: p) a = read();
for (auto &[a, b]: p) b = read(), t.push_back(b);
sort(t.begin(), t.end());
for (auto &[a, b]: p)
b = lower_bound(t.begin(), t.end(), b) - t.begin() + 1;
sort(p.begin(),p.end() ,[](pii a , pii b){
if( a.first != b.first ) return a.first < b.first;
return a.second > b.second;
});
BinaryIndexedTree B(n);
int res = 0;
map<pii,int> cnt;
for( auto it : p ) cnt[it] ++;
for( auto [k,v] : cnt ) res += v*(v-1)/2;
for (auto [a, b]: p)
B.add(b, 1), res += B.calc(n) - B.calc(b-1);
cout << res;
return 0;
}
- Beginner AtCoder Contest 231beginner atcoder contest 231 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 315