CF1213A Chips Moving
考虑是一道非常简单的入门题
就是奇数的个数和偶数的个数取 \(\min\) 即可
code
#include<bits/stdc++.h>
using namespace std;
const int NN = 108;
int n;
int a,cnt[2];
int main(){
scanf("%d",&n);
for(int i = 1; i <= n; ++i){
scanf("%d",&a);
++cnt[a&1];
}
printf("%d",min(cnt[0],cnt[1]));
}
CF1213B Bad Prices
我们从后往前更新答案，每次维护后缀最小值即可
code
#include<bits/stdc++.h>
using namespace std;
const int NN = 2e5 + 8;
int T,n;
int a[NN];
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i = 1; i <= n; ++i) scanf("%d",&a[i]);
int mn = 0x3f3f3f3f,ans = 0;
for(int i = n; i >= 1; --i){
mn = min(a[i],mn);
ans += mn != a[i];
}
printf("%d\n",ans);
}
}
CF1213C Book Reading
这道题目，我们可以发现显然是有周期性的
我们个位数都可以统一成以 \(10\) 为一轮，然后就可以快速求解（预处理周期即可）
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int q;
ll n,m;
int a[10] = {0,45,40,45,40,25,40,45,40,45};
int main(){
scanf("%d",&q);
for(int i = 1; i <= q; ++i){
ll ans = 0;
scanf("%lld%lld",&n,&m);
int base = m % 10;
ll cnt = n / m;
for(int i = 1; i <= cnt % 10; ++i){
ans += i * base % 10;
}
ans += cnt / 10 * a[base];
printf("%lld\n",ans);
}
}
CF1213D Equalizing by Division (EZ&HD)
标签：字符串 \(C^+\)
我们可以发现，最后剩下的数字一定是只剩下高位。
我们这道题可以建出一个 01trie 然后就可以进行求解。
我们按所有数转化为二进制后的长度从小到大推入 01trie
然后我们就可以对于每个节点记录前 \(k\) 个遍历到这个节点的全部将这个节点后面的数字去掉的代价
可以证明从小到大加入后前 \(k\) 个遍历到的一定是最优解之一
最后对于每个节点记录的值取 \(\min\) 即可
code
#include<bits/stdc++.h>
using namespace std;
const int NN = 2e5 + 8;
int n,k;
int a[NN];
string s[NN];
vector<int> ans;
struct Trie{
int son[2];
int num,res;
#define l(x) T[x].son[0]
#define r(x) T[x].son[1]
#define son(x,y) T[x].son[y-'0']
#define num(x) T[x].num
#define res(x) T[x].res
}T[NN << 4];
int cnt = 1;
void insert(int p){
int now = 1;
if(num(now) < k) ++num(now),res(now) += s[p].size();
for(int i = 0; i < s[p].size(); ++i){
if(son(now,s[p][i]) == 0){
son(now,s[p][i]) = ++cnt;
}
now = son(now,s[p][i]);
if(num(now) < k){
++num(now),res(now) += s[p].size() - i - 1;
if(num(now) == k) ans.push_back(res(now));
}
}
}
bool cmp(string &x,string &y){
return x.size() < y.size();
}
int main(){
scanf("%d%d",&n,&k);
for(int i = 1; i <= n; ++i) scanf("%d",&a[i]);
for(int j = 1; j <= n; ++j){
if(a[j] == 0) s[j] = "0";
while(a[j]){
s[j] += (a[j] & 1) + '0';
a[j] >>= 1;
}
reverse(s[j].begin(),s[j].end());
}
sort(s+1,s+1+n,cmp);
for(int i = 1; i <= n; ++i) insert(i);
sort(ans.begin(),ans.end());
printf("%d",ans[0]);
}
CF1213E Two Small Strings
考虑这道题目显然还是很简单
我们考虑构造，很容易想到一种方法就是找到一个 \(abc\) 的排列，最后重复 \(n\) 次
但是我们会发现这样一组数据：
3
ab
ac
我们显然对于上面的一组数据就不能这样构造。
但是我们有另外一组构造方法：\(bbbcccaaa\)
就是对于 \(bca\) 这个排列来说，每个字母重复 \(n\) 遍即可
最后将两个构造方法合并即可通过本题。
code
#include<bits/stdc++.h>
using namespace std;
bool a[3][3];
int n;
char s[10];
int main(){
memset(a,1,sizeof(a));
scanf("%d",&n);
for(int i = 1; i <= 2; ++i){
scanf("%s",s);
a[s[0]-'a'][s[1]-'a'] = 0;
}
if(a[0][0] && a[1][1] && a[2][2]){
for(int i = 0; i <= 2; ++i){
for(int j = 0; j <= 2; ++j){
if(!a[i][j] || i == j) continue;
for(int k = 0; k <= 2; ++k){
if(!a[j][k] || j == k || i == k) continue;
puts("YES");
for(int l = 1; l <= n; ++l) printf("%c",i+'a');
for(int l = 1; l <= n; ++l) printf("%c",j+'a');
for(int l = 1; l <= n; ++l) printf("%c",k+'a');
return 0;
}
}
}
}
else{
for(int i = 0; i <= 2; ++i){
for(int j = 0; j <= 2; ++j){
if(!a[i][j] || i == j) continue;
for(int k = 0; k <= 2; ++k){
if(!a[j][k] || j == k || i == k || !a[k][i]) continue;
puts("YES");
for(int l = 1; l <= n; ++l) printf("%c%c%c",i+'a',j+'a',k+'a');
return 0;
}
}
}
}
}