传送门：这里
这场好难，枯了。
A
分类讨论
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[3];
for(int i=0; i<3; i++) cin>>a[i];
sort(a, a+3);
if(a[0]==a[1] && a[1]!=a[2] || a[0]!=a[1] && a[1]==a[2]) puts("Yes");
else puts("No");
return 0;
}
B
模拟
#include<bits/stdc++.h>
using namespace std;
int main(){
int n; cin>>n;
bool ok=true;
while(n--){
int t; cin>>t;
if(t%2==0){
if(t%3!=0 && t%5!=0) ok=false;
}
}
puts(ok? "APPROVED": "DENIED");
return 0;
}
C
模拟
#include<bits/stdc++.h>
using namespace std;
map<string, int> mp;
int main(){
int n; cin>>n;
while(n--){
string t; cin>>t;
mp[t]++;
}
int num=0;
for(auto i: mp) num=max(num, i.second);
for(auto i: mp) if(i.second==num) cout<<i.first<<endl;
return 0;
}
D
二分答案，看看二分出来的 (v) 在所有数中的排名。麻烦在于求排名的时候也要二分 qwq
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define endl '
'
#define debug(x) cerr << #x << ": " << x << endl
#define pb(a) push_back(a)
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
#define int long long
inline void read(int &x) {
int s=0;x=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-')x=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
x*=s;
}
const int N=2e5+5;
int n, k;
int w[N];
int get_rank(int v){
int rk=0;
rep(i,1,n-1){
int cur=w[i];
if(cur<0){
int L=i+1, R=n;
while(L<R){
int mid=L+R>>1;
if(v>cur*w[mid]) R=mid;
else L=mid+1;
}
if(v>cur*w[L]) rk+=n-L+1;
}
else{
int L=i+1, R=n;
while(L<R){
int mid=L+R+1>>1;
if(v>cur*w[mid]) L=mid;
else R=mid-1;
}
if(v>cur*w[L]) rk+=L-i;
}
}
rk++;
// debug(rk);
return rk;
}
signed main(){
read(n), read(k);
rep(i,1,n) read(w[i]);
sort(w+1, w+1+n);
int l=-1e18, r=1e18;
while(l<r){
int mid=l+r+1>>1;
if(get_rank(mid)<=k) l=mid;
else r=mid-1;
}
cout<<l<<endl;
return 0;
}
E
分析
我们采取 dp 的做法。
为了直观地考虑这个问题，我们将原串用 (a) 表示，根据题意，我们的目标是最小化 (sum (b_i+c_i)) （求最小代价）。
(egin {array}{ccc} &a_n&a_{n-1}&...&a_1\ +&b_n&b_{n-1}&...&b_1\ hline =&c_n&c_{n-1}&...&c_1 end {array})
不失一般性，考察第 (i) 位，分成两种情况讨论：
-
第 (i) 位发生进位。
-
第 (i) 位不发生进位。
对于第一种情况：
我们有 (a_i + b_i = 10 + c_i) （因为发生了进位），要最小化 (b_i + c_i) ，
因为 (b_i + c_i = 2b_i + a_i - 10) ，我们只需要最小化 (b_i) ，故让 (b_i = 10 - a_i) 即可，相应地，可得 (c_i = 0)
类似地，在第二种情况中可得相应的 (b_i = 0,~ c_i = a_i)
下面开始 dp：(f[i][0/1]) 表示第 (i) 位不进位 / 进位下前 (i) 位的最小代价。
如果第 (i-1) 位没有发生进位，那么第 (i) 位没有受到影响，直接针对上面的讨论进行转移即可。
如果发生进位，那么第 (i) 位的 (a_i) 相当于 (a_i+1) 类似地进行转移。
结合转移方程理解：
[f[i][0]=min(f[i-1][0]+a[i], ~f[i-1][1]+a[i]+1)
]
[f[i][1]=min(f[i-1][0]+10-a[i],~ f[i-1][1]+10-1-a[i]);
]
代码：
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
int t(char ch){ // char 转 int
return ch-'0';
}
const int N=1e6+5;
int f[N][2];
int main(){
string s; cin>>s; int n=s.size(); reverse(s.begin(), s.end()); s=' '+s;
f[0][1]=1, f[0][0]=0;
rep(i,1,n){
f[i][0]=min(f[i-1][0]+t(s[i]), f[i-1][1]+t(s[i])+1);
f[i][1]=min(f[i-1][0]+10-t(s[i]), f[i-1][1]+10-1-t(s[i]));
}
cout<<min(f[n][1]+1, f[n][0]);
return 0;
}