AtCoder Beginner Contest 155

A.水题
一开始想到的是map，但是题太水了，不值得用

#include<bits/stdc++.h>

using namespace std;

int main(){
	int a,b,c;
	cin>>a>>b>>c;
	bool flag =0;
	if(a == b && a != c){
		flag =1;
		cout<<"Yes"<<endl;
	}
	if(a == c && a != b){
		flag =1;
		cout<<"Yes"<<endl;
	}
	if(b ==  c && b != a){
		flag =1; 
		cout<<"Yes"<<endl;
	}
	if(!flag)
		cout<<"No"<<endl;
		
	
	return 0;
} 

B
水题：
读懂就能做的那种

#include<bits/stdc++.h>

using namespace std;

int a[105];
int b[105];
int main(){
	int n;
	cin>>n;
	int k = 0;
	int flag = 0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i] % 2 == 0){
			b[k] = a[i];
			k++;
		}
	}
	for(int i=0;i<k;i++){
		if(b[i]%3 == 0 || b[i]%5==0){
			continue;
		}
		else{
			flag = 1;
			break;
		}
	}
	if(flag) cout<<"DENIED"<<endl;
	if(!flag) cout<<"APPROVED"<<endl;
	return 0;
} 

C
还是水！！，不过满足了我想练习使用map的愿望

#include<bits/stdc++.h>
#define maxn 200000+5
#define inf 0x3f3f3f3f
using namespace std;

string a[maxn];
string s;
map<string,int> st;

int main(){
	int n;
	cin>>n;
	int maxx = -inf;
	for(int i=0;i<n;i++){
		cin>>a[i];
		st[a[i]]++;
		maxx = max(st[a[i]],maxx);
	}
	int len = st.size();
	for(auto i=st.begin();i!=st.end();i++){
		//cout<<i->first<<" "<<i->second<<endl;
		if(i->second == maxx){
			cout<<i->first<<endl;
		}
	}
	return 0;
} 

D.一拿到D题首先我是开心的，因为好像杭电里面有一个求前n项最大的值几乎一样

RE（不知道为什么）
一开始以为b数组不够大，特地尽可能的大了，但还是不对！！
这个题浪费了很多时间！！！
最后结束了才看榜单没有很多人做出来，500多人
我的code

#include<algorithm>
#include<iostream>
#define maxn 200000+5

using namespace std;
typedef long long ll;

const ll maxx = 1e10+5;

ll a[maxn];
ll b[maxx+maxx];


int main(){
	//ios::sync_with_stdio(false);
	//cin.tie(0);
	//cout.tie(0);
	ll n,k;
	cin>>n>>k;
	ll num = 0;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			b[num] = a[i]*a[j];
			num++;
		}
	}
	sort(b,b+(n*(n-1))/2);
	cout<<b[k-1]<<endl;
	return 0;
}

结束后看大佬们的代码，发现大多数都是二分做的

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5;
int a[N],n;
ll k;
ll ceil(ll x,ll y) {
    if(x>=0) return x/y;
    return (-x-y-1)/(-y);
}
ll floor(ll x,ll y) {
    if(x>=0) return x/y;
    return -(-x+y-1)/y;
}
ll cal() {
    ll l=-1e18,r=1e18;
    while(l<=r) {
        ll mid=(l+r)>>1,cnt=0;
        for(int i=1;i<=n;i++) {
            if(a[i]==0) {
                if(mid<0) cnt+=n;
            }
            else if(a[i]<0) {
                int x=lower_bound(a+1,a+n+1,ceil(mid,a[i]))-a-1;
                cnt+=x;
            }
            else {
                int x=upper_bound(a+1,a+n+1,floor(mid,a[i]))-a-1;
                cnt+=n-x;
            }
        }
        for(int i=1;i<=n;i++) {
        	if(1LL*a[i]*a[i]>mid) cnt--;
        }
        cnt/=2;
        //printf("%lld %lld\n",mid,cnt);
        if(cnt<k) r=mid-1;
        else l=mid+1;
    }
    return l;
}
int main() {
    scanf("%d%lld",&n,&k);
    k=1LL*(n-1)*n/2+1-k;
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1);
    ll ans=cal();
    printf("%lld\n",ans);
    return 0;
}

E
这个题我感觉是能做的，但是D耗时太长，就没时间了，就是求硬币的最小值，我感觉贪心（可能最近贪心练多了）

MY code 对 99 这种数据就不满足！！！

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

string s;

int main(){
	cin>>s;
	ll num = 0;
	ll l = s.length();
	
	for(int i=0;i<l;i++){
		int res = s[i] - '0';
		if(res < 5){
			num += res;
		}
		if(res>5){
			num += 1;
			num = num+ (10-res);
		}
		if(res == 5){
			num += 5;
		}
	}
	cout<<num<<endl;
	return 0;
}

大佬的code 还不是很理解，但是做了好多这样的区间变动的题了，都不会，垃圾啊

#include<bits/stdc++.h>
using namespace std ;
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define re register
#define int long long
int gi() {//快读 
	char cc = getchar() ; int cn = 0, flus = 1 ;
	while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
	while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
	return cn * flus ;
}
const int N = 1e6 + 5 ; 
char s[N] ; 

int f[N][2] ;

signed main()
{
	scanf("%s", s + 1 ) ;
	int n = strlen( s + 1 ), Ans = 0 ; s[0] = '0' ;
	f[n + 1][0] = 0, f[n + 1][1] = 100 ;
	for( re int i = n; i >= 0; -- i ) {
		int u = s[i] - '0' ; 
		f[i][1] = min( f[i + 1][1] - u - 1, f[i + 1][0] - u ) + 10 ;
		f[i][0] = min( f[i + 1][1] + u + 1, f[i + 1][0] + u ) ;
	}
	cout << f[0][0] << endl ;
	return 0 ;
}