codeforces补题

Codeforces Round #702 (Div. 3)

A-Dense Array：贪心 

#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 1005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;

using namespace std;

int a[55];
void solve()
{
	int t,n,k,x;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i = 1; i <= n; i++){
			scanf("%d",&a[i]);
		}
		int ans = 0;
		for(int i = 1; i < n; i++){
			if((a[i]+a[i+1]-1)/a[i+1] > 2){
				int temp = a[i+1];
				while(temp < a[i]){
					temp *= 2;
					ans++;
				}
				ans--;
			}
			else if((a[i+1]+a[i]-1)/a[i] > 2){
				int temp = a[i];
				while(temp < a[i+1]){
					temp *= 2;
					ans++;
				}
				ans--;
			}
		}
		printf("%d\n",ans);
	} 
}

int main()
{
	solve();
	return 0;
}

B-Balanced Remainders：贪心 

#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 1005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;

using namespace std;

int a[55];
void solve()
{
	int t,n,k,x,d0,d1,d2;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		d0 = d1 = d2 = 0;
		for(int i = 1; i<= n; i++){
			scanf("%d",&x);
			if(x%3 == 0) d0++;
			if(x%3 == 1) d1++;
			if(x%3 == 2) d2++; 
		}
//		cout << d0 << " " << d1 << " " << d2 << endl;
		int ans = 0,k = n/3;
		if(d0 < k){
			int p = k-d0;
			if(d2 > k) {
				ans += min(p,d2-k);
				
				d0 += min(p,d2-k);
				d2 -= min(p,d2-k);
			}
			if(d0 < k){
				if(d1 > k){
					ans += 2*(k-d0);
					d1 -= k-d0;
					d0 += k-d0;
				}
			}
		}
		if(d1 < k){
			int p = k-d1;
			if(d0 > k) {
				ans += min(p,d0-k);	
				d1 += min(p,d0-k);
				d0 -= min(p,d0-k);
			}
			if(d1 < k){
				if(d2 > k){
					ans += 2*(k-d1);
					d2 -= k-d1;
					d1 += k-d1;
				}
			}
		}
		if(d2 < k){
			int p = k-d2;
			if(d1 > k) {
				ans += min(p,d1-k);
				d2 += min(p,d1-k);
				d1 -= min(p,d1-k);
			}
			if(d2 < k){
				if(d0 > k){
					ans += 2*(k-d2);
					d0 -= k-d2;
					d2 += k-d2;
				}	
			}
		}
		printf("%d\n",ans);
	} 
}

int main()
{
	solve();
	return 0;
}

C-Sum of Cubes：公式变形

pow赋值给int的时候：指数用常量，结果正确；指数用int、double，结果错误

pow赋值给double的时候，指数用常量、int、double，结果都正确 

#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 1005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;

using namespace std;

void solve()
{
	int t;
	ll x;
	scanf("%d",&t);
	while(t--){
		scanf("%lld",&x);
		int flag = 0;
		ll i;
		for(i = 1; i*i*i < x; i++){
			double k = x-i*i*i;
			ll p = pow(k,1.0/3)+0.5;
			if(p*p*p == k){
				flag = 1;
				break;
			}
		}
		if(flag) puts("YES");
		else puts("NO");
	} 
}

int main()
{
	solve();
	return 0;
}

D-Permutation Transformation：树形dp 

#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 1005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;

using namespace std;

int a[105],d[105],n;
vector<int>tree[105];
void build(int l,int r,int xb)
{
	int lmmax = 0,lxb = 0,rmmax = 0,rxb = 0;
	if(l <= xb-1){
		for(int i = l; i < xb; i++){
			if(lmmax < a[i]){
				lmmax = a[i];
				lxb = i;
			}
		}
		tree[a[xb]].push_back(a[lxb]);
		tree[a[lxb]].push_back(a[xb]);
		build(l,xb-1,lxb);
	}
//	cout << lxb << endl;
	if(xb+1 <= r){
		for(int i = xb+1; i <= r; i++){
			if(rmmax < a[i]){
				rmmax = a[i];
				rxb = i;
			}
		}
//	cout << rxb << endl;
		tree[a[xb]].push_back(a[rxb]);
		tree[a[rxb]].push_back(a[xb]);
		build(xb+1,r,rxb);
	}
}

void dfs(int s,int f)
{
    for(int i = 0; i < tree[s].size(); i++){
    	int v = tree[s][i];
    	if(v == f) continue;
    	d[v] = d[s]+1;
    	dfs(v,s);
	}
}

void solve()
{
	int t;
	scanf("%d",&t);
	while(t--){
		memset(d,0,sizeof(0));
		scanf("%d",&n);
		int mmax = 0,xb = 0;
		for(int i = 1; i <= n; i++){
			scanf("%d",&a[i]);
			if(a[i] > mmax){
				mmax = a[i];
				xb = i;
			}
		}
		build(1,n,xb);
		d[a[xb]] = 0;
		dfs(a[xb],0);
		for(int i = 1; i <= n; i++){
			printf("%d ",d[a[i]]);
			tree[a[i]].clear();
		}
		printf("\n");
	} 
}

int main()
{
	solve();
	return 0;
}

E-Accidental Victory：前缀和 

#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 200005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;

using namespace std;

struct Nod{
    ll num;
    int xb; 
}node[N];

bool cmp(Nod a,Nod b)
{
    return a.num < b.num;
}

ll pre[N];
int ans[N];
void solve()
{
    int t,n;
    scanf("%d",&t);
    while(t--){
        memset(pre,0,sizeof(pre));
        memset(ans,0,sizeof(ans));
        scanf("%d",&n);
        for(int i = 0; i < n; i++){
            scanf("%d",&node[i].num);
            node[i].xb = i;
        }
        sort(node,node+n,cmp);
        pre[0] = node[0].num;
        for(int i = 1; i < n; i++) pre[i] = pre[i-1]+node[i].num;
        ans[node[n-1].xb] = 1;  
        int cnt = 0;
        for(int i = n-2; i >= 0; i--){
            if(pre[i] >= node[i+1].num){
                ans[node[i].xb] = 1;
                cnt++;
            }
            else break;
        }
        printf("%d\n",cnt+1);
        for(int i = 0; i < n; i++){
            if(ans[i]) printf("%d ",i+1);
        }
        printf("\n");
    } 
}

int main()
{
    solve();
    return 0;
}

F-Equalize the Array：前缀和+二分查找 

#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 200005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;

using namespace std;

int a[N],b[N],pre[N]; 
map<int,int>mp;
void solve()
{
	int t,n;
	scanf("%d",&t);
	while(t--){
		int n,mmax = 0;
		mp.clear();
		scanf("%d",&n);
		for(int i = 0; i < n; i++){
			scanf("%d",&a[i]);
			mp[a[i]]++;
			mmax = max(mmax,mp[a[i]]);
		} 
		sort(a,a+n);
		int m = unique(a,a+n)-a;
		for(int i = 0; i < m; i++){
			b[i] = mp[a[i]];
		}
		sort(b,b+m);
		pre[0] = b[0];
		for(int i = 1; i < m; i++){
			pre[i] = pre[i-1]+b[i];
		}
		int ans = N*2;
		for(int i = 0; i <= mmax; i++){
			int suf,sum = 0,xb1,xb2;
			xb1 = lower_bound(b,b+m,i)-b;
			if(b[xb1] == i) sum += pre[xb1-1];
			else {
				if(xb1 == 0) sum += 0;
				else sum += pre[xb1-1];
			}
			xb2 = upper_bound(b,b+m,i)-b;
			if(xb2 == 0) suf = pre[m-1];
			else suf = pre[m-1]-pre[xb2-1];
			sum += suf-i*(m-xb2);
			ans = min(ans,sum); 
		}
		printf("%d\n",ans);
	} 
}

int main()
{
	solve();
	return 0;
}

G-Old Floppy Drive：最大前缀和+二分查找

大意：给出一组数a，m次询问，每次询问x，从数组a的第一个数开始依次往后取数，如果到了最后一个再从第一个重新开始取，并对这些数求和，问和大于等于x的最少取数次数。
思路：如果一次循环内就可以使得和大于等于x，那么问题就转化为了数组a的前缀和中大于等于x的最小下标是哪个（问题精髓），因为负数的存在，前缀和不满足单调性，不能直接查找，那么我们维护出每个点的前缀和的最大值，就可以使得前缀和满足单调性。如果不是一次循环，那么d*pre[n]+k>=x，我们要尽可能使得d小，那么就要k越大越好，所以k取最大前缀和mpre[n]，利用k求出d后再到mpre(最大前缀和)中找到大于等于剩下的数的下标。 
#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 200005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;

using namespace std;

ll a[N];
ll mpre[N];
ll pre[N];
void solve()
{
	int t,n,m;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		memset(pre,0,sizeof(pre));
		memset(mpre,0,sizeof(mpre));
		for(int i = 1; i <= n; i++){
			scanf("%lld",&a[i]);
			pre[i] = pre[i-1]+a[i];
		}
		mpre[1] = pre[1];
		for(int i = 2; i <= n; i++){
			if(pre[i] > mpre[i-1]){
				mpre[i] = pre[i];
			}
			else mpre[i] = mpre[i-1];
		}
		while(m--){
			ll x;
			scanf("%lld",&x);
			ll ans;
			if(x <= mpre[n]){
				ans = (lower_bound(mpre+1,mpre+n+1,x)-mpre)-1;
				printf("%lld ",ans);
			}
			else{
				if(pre[n] <= 0) printf("-1 ");
				else{
					int d = (x-mpre[n]+pre[n]-1)/pre[n];
					ll cnt = 1ll*d*1ll*n;
					ll k = x-d*pre[n];
					ans = cnt+(lower_bound(mpre+1,mpre+n+1,k)-mpre)-1;//注意lower_bound单独写在括号内。
					printf("%lld ",ans);
				}		
			}	
		}
		printf("\n");
	}
}

int main()
{
	solve();
	return 0;
}








Codeforces Round #700 (Div. 2)

D1-Painting the Array I：贪心

大意：给出一组数，给这组数涂色，只有0和1两种颜色，将涂了相同颜色的数按保持原数组的相对位置放入一个数组内，这样就会形成两个数组，定义S，表示合并数组相邻相同元素后数组内剩余的元素个数。求S(0)+S(1)的最大值。
思路：先构造出两个集合去存放数字，因为要保持相对位置不变，所有在考虑a[i]放入那个集合是，我们只需要和两个集合末尾的元素比较，假设两个末尾元素分别是p0,p1，如果p0 = p1 = a[i]，放入哪个集合对答案的贡献都为0，所有我们要尽量避免两个集合末尾的元素相同，这样在某个集合末尾元素和a[i]相同时，我们可以考虑放另外一个集合，所有如果p0 != a[i] ,p1 != a[i],p1 != a[i+1]的话，我们就让a[i]放入p1集合中，并更新p1,否则就放入p0集合中，并更新p0。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 100005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;

using namespace std;

int a[100005];
void solve()
{
	int n;
	scanf("%d",&n);
	for(int i = 1; i <= n; i++){
		scanf("%d",&a[i]);
	}
	a[n+1] = 0;
	int p0,p1;
	if(n == 1) {
		printf("%d",1);
		return;
	}
	int ans = 1;
	p0 = a[1],p1 = 0;
	for(int i = 2; i <= n; i++){
		if(p0 != a[i]){
			ans++;
			if(p0 != a[i+1] && p1 != a[i])
			    p1 = a[i];
			else p0 = a[i];
		}
		else{
			if(p1 != a[i]){
				ans++;
				p1 = a[i];
			}
		}
	}
	printf("%d",ans);
}

int main()
{
	solve();
	return 0;
}

Codeforces Round #699 (Div. 2)

C-Fence Painting

大意：给出n个围栏，围栏上原始的颜色为a1,a2...an,现在想为这n个围栏涂上颜***1,b2...bn,现在请来了m个师傅，每个师傅只能涂一种颜色ci，师傅一定会对某一个围栏涂色，并且师傅来的顺序为1-m，问m个师傅涂完颜色后，最后的围栏的颜色是否能成为之前想设计成的颜色？
思路：刚开始看错题了，以为师傅是同时到的，后面才发现是有顺序的。现在考虑两种情况。
1）ai == bi，不用涂
2）ai != bi，看师傅存在师傅cj，cj=bi，不存在的话，答案为NO，存在则继续往下看。
如果有师傅cj要涂的颜色在b中不存在，他又必需要找一个围栏涂色，为了能达到理想的颜色，那么这个师傅涂的围栏一定要是存在后面的师傅能够将这个围栏涂成设计好的颜色。那如何判断呢？如果从前往后看的话，我们不能知道后面的情况，但我们从后往前看，如果我们在后面找到了一个师傅要涂的颜色在b中存在，我们将他要涂的围栏用post标记，前面不存在的师傅都涂这个围栏，那么之后让后面这个师傅覆盖前面师傅涂的颜色就够了。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 100005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;

using namespace std;

int a[N],b[N],c[N],cnt[N],ans[N];
vector<int>xb[N];
void solve()
{
	int t,n,m;
	scanf("%d",&t);
	while(t--){
		memset(ans,0,sizeof ans);
		memset(cnt,0,sizeof cnt);
		scanf("%d%d",&n,&m);
		for(int i = 1; i <= n; i++){
			scanf("%d",&a[i]);
		//	cnt[a[i]] = i;
		}
		for(int i = 1; i<= n; i++){
			scanf("%d",&b[i]);
			cnt[b[i]] = i;
		}
		for(int i = 1; i <= m; i++){
			scanf("%d",&c[i]);
			xb[c[i]].push_back(i);
		}
		int flag = 0;
		for(int i = 1; i <= n; i++){
			if(a[i] != b[i]){
				int siz = xb[b[i]].size();
				if(!siz){
					flag = 1;
					break;
				}
				ans[xb[b[i]][0]] = i;
				xb[b[i]].erase(xb[b[i]].begin()+0);
			//	cout << b[i] << endl;
			}
		}
		if(flag) puts("NO");
		else{
			int post = 0;
			for(int i = m; i >= 1; i--){
				if(!ans[i]){
					if(!post){
						if(cnt[c[i]]) {
							ans[i] = cnt[c[i]];
							post = ans[i];
						}
						else{
						//	cout << c[i] << "\n";
							flag = 1;
				        	break;
						}
						
					}
					else ans[i] = post;
				}
			    else	post = ans[i];
			} 
			if(flag) puts("NO");
			else{
				puts("YES");
				for(int i = 1; i <= m; i++){
					printf("%d ",ans[i]);
				}
				printf("\n");
			}
		}
			for(int i = 1; i <= m; i++){
			xb[c[i]].clear();
	    	}
		}
	
}

int main()
{
	solve();
	return 0;
}

D-ABGraph：画图找规律

大意：给出一张含有n条边且没有自环的有向图，每两个点之间有两条边，边的权值要么是'a'，要么是‘b’,问是否存在长度为m的路径(路径由经过的字符顺序组成)，使得路径为回文串。
思路：首先如果存在两个点之间的两条边的权值相同，那么在这两个点之间循环走就够了，但如果不存在呢？那就是说两个点之间的边权值是a和b，那如果m是奇数的话，同样在这两个点之间循环走就能走出回文串(可以动手画画)。现在考虑m是偶数的情况，我们可以发现如果能够找到3个点u,v,w,使得入v的边权值等于出v的边权值，那就在这三个点之间循环走就够了，同时还要考虑m是不是4的倍数，如果数，那就从v开始走，如果不是，那就从u或v开始走。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 100005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;

using namespace std;

char grap[1005][1005];
int xb[1005][2];
void solve()
{
	int t,n,m;
	scanf("%d",&t);
	while(t--){
		memset(xb,0,sizeof xb);
		scanf("%d%d",&n,&m);
		getchar();
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				scanf("%c",&grap[i][j]);
				if(grap[i][j] == 'a' && !xb[i][0]) xb[i][0] = j;
				if(grap[i][j] == 'b' && !xb[i][1]) xb[i][1] = j;
			}
			getchar();
		}
		int loop = 0,lv,lu,u,v,w;
		u = v = w = 0;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				if(i != j){
					if(grap[i][j] == grap[j][i]){
						loop = 1;
						lu = i;
						lv = j;
						break;
					}
					if(u) continue;
					if(grap[i][j] == 'a'){
						if(xb[j][0]){
							u = i;
							v = j;
							w = xb[j][0];
						}
						continue;
					}
					if(grap[i][j] == 'b'){
						if(xb[j][1]){
							u = i;
							v = j;
							w = xb[j][1];
						}
					}
				}
			}
		}
		if(loop){
			puts("YES");
			for(int i = 1; i <= m+1; i++){
				if(i&1) printf("%d ",lu);
				else printf("%d ",lv);
			}
			printf("\n");
		}
		else{
			if((m&1)){
				puts("YES");
				for(int i = 1; i <= m+1; i++){
					if(i&1) printf("%d ",1);
					else printf("%d ",2);
				}
				printf("\n");
			}
			else{
				if(!u){
					puts("NO");
				}
				else{
					puts("YES");
					if(m%4){
						for(int i = 1; i <= m+1; i++){
							if(i%4 == 1) printf("%d ",u);
							if(i%4 == 2) printf("%d ",v);
							if(i%4 == 3) printf("%d ",w);
							if(i%4 == 0) printf("%d ",v);
						}
					}
					else{
						for(int i = 1; i <= m+1; i++){
							if(i%4 == 1) printf("%d ",v);
							if(i%4 == 2) printf("%d ",w);
							if(i%4 == 3) printf("%d ",v);
							if(i%4 == 0) printf("%d ",u);
						}
					}
					printf("\n");
				}	
			}
		}
	}
}

int main()
{
	solve();
	return 0;
}




Codeforces Round #698 (Div. 2)

B-Nezzar and Lucky Numbers

题意：给定某个数d(1<= d <=9),如果某个数至少存在一个d那么称这个数为幸运数，给定某个数，问这个数能否拆成几个幸运数的和？
思路：
1：如果x < 10*d,那么幸运数的十位不可能是d，那么这个幸运数一定是m*10+n*d，即x的个位与几个d的和的个位相同，只要判断m是否存在即可（m>=0）。
2：如果x >= 10*d, 那么一定可以拆分。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 911451407;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;
 
using namespace std;
 
int main()
{
	int t,q,d,x;
	cin >> t;
	while(t--){
		cin >> q >> d;
		for(int i = 1; i <= q; i++){
			cin >> x;
			int flag = 0;
			if(x >= d*10) cout << "YES\n";
			else{
				flag = 0;
				for(int j = 1; j <= 10; j++){
					if(x%10 == (j*d)%10){
						if(j*d == x) cout << "YES\n";
						else if(x-j*d>=10) cout <<"YES\n";
						else cout << "NO\n";
						flag = 1;
						break;
					}
				}
				if(!flag) cout <<"NO\n";
			}
			
		}
	}
 	return 0;
}

Codeforces Round #697 (Div. 3)

A-Odd Divisor：找规律

大意：给出一个数n，问n有没有大于1的奇数因子。
思路：奇数肯定有，偶数的话，只要是2的倍数那都没有，其它都有。怎么判断2的倍数，10，100，1000，10000，所有二进制只有一个1就是2的倍数。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 100005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;

using namespace std;

void solve()
{
	int t;
	ll n;
	scanf("%d",&t);
	while(t--){
		scanf("%lld",&n);
		if(n&1) puts("YES");
		else{
			int cnt = 0;
			while(n){
				if(n&1) cnt++;
				n >>= 1;
			}
		if(cnt == 1)	puts("NO");
		else puts("YES");
		}
	} 
}

int main()
{
	solve();
	return 0;
}

B-New Years' Number：打表+枚举 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 1000005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;

using namespace std;

bool vis[N];

void init()
{
	for(int i = 0; i <= 1000; i++){
		for(int j = 0; j <= 1000; j++){
			int res = 2020*i + 2021*j;
			if(res < 2020) vis[res] = false;
			else if(res > 1000000) continue;
			else {
				vis[res] = true;
			} 
		}
	}
}

void solve()
{
	init();
	int t;
	int n;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		if(vis[n]) puts("YES");
		else puts("NO");
	} 
}

int main()
{
	solve();
	return 0;
}

C-Ball in Berland：数学+思维

https://codeforces.com/contest/1475/problem/C
大意：有a个男孩，b个女孩，舞蹈表演需要一男一女组合搭配表演，并且每个班要派出两组，现在已知k组搭配关系，问有多少种派法(不能派一个人在两个搭配关系中的两组)。
思路：不需要用到a，b。分别统计每个男孩和女孩在k组搭配关系中出现了几次，假设这个男孩出现了x次，女孩出现了y次，那剩下的k-x组内不存在这个男孩，但可能存在与这个男孩搭配的女孩，所以还有再减去女孩出现的次数加+1，所有这个男孩对答案的贡献就为k-x-(y-1).注意开long long。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 200005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;

using namespace std;

int a_cnt[N],b_cnt[N];
int ax[N],bx[N];
void solve()
{
	int t,a,b,k,x;
	scanf("%d",&t);
	while(t--){
		memset(a_cnt,0,sizeof(a_cnt));
		memset(b_cnt,0,sizeof(b_cnt));
		scanf("%d%d%d",&a,&b,&k);
		a = 0,b = 0;
		for(int i = 1; i <= k; i++) {
			scanf("%d",&ax[i]);
			if(a_cnt[ax[i]] == 0) a++;
			a_cnt[ax[i]]++;	
		}
		for(int i = 1; i <= k; i++){
			scanf("%d",&bx[i]);
			if(b_cnt[bx[i]] == 0) b++;
			b_cnt[bx[i]]++;	
		}
		ll ans = 0;
		for(int i = 1; i <= k; i++){
		//    if(k-a_cnt[ax[i]]-b_cnt[bx[i]]+1 < 0) continue;
			ans += abs(1ll*k-1ll*a_cnt[ax[i]]-1ll*b_cnt[bx[i]]+1);
		}
		printf("%lld\n",ans/2);
	} 
}

int main()
{
	solve();
	return 0;
}

D-Cleaning the Phone：贪心+前缀和+二分

大意：给出一组含有n个数的数组a，同时给出另一个含n个数的数组b，对应a数组每个数的价值，价值要么是1，要么是2。给出m，从数组a取若干个数求和，问和至少为m的最小价值是多少。
思路：一看以为是01背包，再看下数据范围果断肯定不是背包，既然求最小，那就往贪心方面走。考虑从a中取多少个数，同时从b中取多少个数，又因为在取价值相同的两个数是，我们优先取更大的数，所有先将价值为1的放进数组v1,价值为2的放进数组v2，并从大到小排序。根据前面的贪心策略，我们优先取数组前面的元素，并用前缀和来维护取多少个数的和。然后我们就可以枚举a，求出差值然后在b中分查找还需要补多少. 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 200005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;

using namespace std;

bool cmp(int x,int y)
{
	return x > y;
}

int a[N];
ll v1[N],v2[N];
void solve()
{
	int t,n,m,x;
	scanf("%d",&t);
	while(t--){
		int n1 = 0,n2 = 0;
		scanf("%d%d",&n,&m);
		for(int i = 1; i <= n; i++){
			scanf("%d",&a[i]);
		}
		for(int i = 1; i <= n; i++){
			scanf("%d",&x);
			if(x == 1) v1[++n1] = a[i];
			else v2[++n2] = a[i];
		}
		sort(v1+1,v1+n1+1,cmp);
		sort(v2+1,v2+n2+1,cmp);
		v1[n1+1] = 0;
		v2[n2+1] = 0;
		for(int i = 1; i <= n1; i++) v1[i] += v1[i-1];
		for(int i = 1; i <= n2; i++) v2[i] += v2[i-1];
		if(v1[n1]+v2[n2] < m){
			printf("-1\n");
			continue;
		}
		int ans = 0x3f3f3f,xb;
		ll res;
		//枚举选多少个1，从0个开始. 
		for(int i = 0; i <= n1; i++){
			res = 1ll*m - v1[i];
			xb = lower_bound(v2+1,v2+1+n2,res) - v2;
			if(v1[i]+v2[xb] >= m) ans = min(ans,i+xb*2);
			xb--;
			if(v1[i]+v2[xb] >= m) ans = min(ans,i+xb*2);
		}
		printf("%d\n",ans);
	} 
}

int main()
{
	solve();
	return 0;
}

E-Advertising Agency：组合数学

大意：给出一个含有n个数的数组，让你选k个数使得这k个数的和最大，问有多少种取法使得和最大。
思路：先给数组排好序，首先要知道的是一定会取数组最后k个数，又因为固定取k个数，分两种情况讨论
1）取的k个数相同，假设是x，那么一定不可能再取与x不同的数，所有也就是再cnt[x]中取k个数有多少取法，排列组合求下。
2）取的k个数存在不同的数，假设其中最小的是y，比y大的数都已经固定，不可能变，假设k个数中存在k1个y，那么答案就是cnt[y]中k1个数有多少种取法。
因为涉及到取模，用初始化杨辉三角取模简单，就不用去搞逆元了。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 1005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;

using namespace std;

ll yh[1005][1005];
void init()
{
	for(int i = 0; i <= 1000; i++){
		yh[i][0] = 1;
		yh[i][i] = 1;
		for(int j = 1; j < i; j++){
			yh[i][j] = (yh[i-1][j-1]+yh[i-1][j])%mod;
		}
	}
}

int a[N],cnt[N];
void solve()
{
	init();
	int t,n,k,x;
	scanf("%d",&t);
	while(t--){
		memset(a,0,sizeof(a));
		memset(cnt,0,sizeof(cnt));
		scanf("%d%d",&n,&k);
		for(int i = 0; i < n; i++){
			scanf("%d",&a[i]);
			cnt[a[i]]++;
		}
		sort(a,a+n);
		int m = unique(a,a+n)-a;	
		if(cnt[a[m-1]] >= k){
			printf("%lld\n",yh[cnt[a[m-1]]][k]);
		}
		else{
			for(int i = m-1; i >= 0; i--){
				if(cnt[a[i]] >= k){
					printf("%lld\n",yh[cnt[a[i]]][k]);
					break;
				}
				k -= cnt[a[i]];
			}
		}
	} 
}

int main()
{
	solve();
	return 0;
}

G-Strange Beauty：动态规划

大意：给出一组数，让你去掉最少的数使得数组中的任意两个数ai,aj ai%aj==0 或者 aj%ai==0
思路：正向走比较麻烦，我们反过来做，也就是求数组剩余数最多是多少。先对数组排好序，那么对于某个数a[i]，我们只需要考虑前面的数有没有它的因子，不需要考虑后面的数了。
令dp[i]表示保留数i的剩余最多数。
遍历a[i]的因子，那么dp[a[i]] = max(dp[a[i]],dp[j]+1)(j是a[i]的因子)，但是时间复杂度是,会T，那么就先用n*ln(n)的时间内处理出所有数的因子放在容器vector内，注意取因子数要从大到小，如果从小到大当j=a[i]是会出错。 
#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 200005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
 
using namespace std;
 
int a[N];
int dp[N]; 
vector<int>d[N];
void solve()
{
	int n,mmax=0;
	scanf("%d",&n);
	for(int i = 1; i <= n; i++) scanf("%d",&a[i]),mmax=max(mmax,a[i]);
	for(int i = 1; i <= mmax; i++){
		for(int j=i; j <= mmax; j += i){
			d[j].push_back(i);
		}
	}
	sort(a+1,a+n+1);
	memset(dp,0,sizeof(dp));
	for(int i = 1; i <= n; i++){
		for(int j = d[a[i]].size()-1; j >= 0; j--){
			dp[a[i]] = max(dp[a[i]],dp[d[a[i]][j]]+1);
		}
	}
	for(int i = 1; i <= mmax; i++){
		d[i].clear();
	}
	int ans = 0;
	for(int i = 1; i <= n; i++){
		ans = max(ans,dp[a[i]]);
	}
	printf("%d\n",n-ans);
}
 
int main()
{
	int t;
	scanf("%d",&t);
	while(t--){
		solve();
	}
}
全部评论

相关推荐

12-26 21:23
已编辑
门头沟学院 golang
双非计算机秋招总结，附带一些个人建议
bg：双非计算机本科，acmer，一段大厂后端实习offer情况：以下是个人秋招获得的offer，最后选择了腾讯后端开发。小马智行：16薪&nbsp;+&nbsp;股票&nbsp;+&nbsp;签字费，base广州京东：20薪&nbsp;+&nbsp;签字费，base北京美团：15.5薪，base北京腾讯：17薪&nbsp;+&nbsp;股票&nbsp;+&nbsp;签字费，base广州面试情况：共计30+技术面，覆盖后端，客户端，数据引擎开发，游戏服务端，智能驾驶，音视频等...网易雷火游戏服务端：一面&nbsp;+&nbsp;二面&nbsp;+&nbsp;三面&nbsp;+&nbsp;hr面网易雷火游戏客户端（服务端是绿通，不冲突流程）：笔试&nbsp;+&nbsp;交叉A面&nbsp;+&nbsp;交叉B面炎魂网络游戏服务器：笔试&nbsp;+&nbsp;一面&nbsp;+&nbsp;二面百度后端：笔试&nbsp;+&nbsp;一面挂米哈游游...
点赞 评论 收藏
分享
12-25 13:56
新国都_Java研发工程师(准入职员工)
图拉斯内推，图拉斯内推码
ai面总结：AI调教的很好，问的问题很有意思，整场面试不会有很大的压迫感，追问大多是根据你的回答提问。总时长：35分钟Q1:自我介绍，重点介绍一下个人背景和大学期间的主要经历。Q2：你对于在一家公司长期发展有什么看法？你认为哪几点因素会让你在一家公司长期工作？（有追问）Q3：你取得过的最大成就是什么？过程中最大的难点是什么？你是如何突破的？最终的结果怎么样？（有追问2个）Q4：请描述一个过往遇到的最有压力困难或最具挑战的一个场景，你是如何解决的？对你有什么影响？（有追问）Q5：依你的看法，请描述一个你近期完成的项目任务，如果重来一次，你会做哪些不同的事情来提升结果？（有追问2个）Q6：电商运营...
点赞 评论 收藏
分享
11-15 14:35
南京邮电大学 Java
27准备日常实习，请狠狠拷打简历
程序员牛肉：你这简历有啥值得拷打的？在牛客你这种简历一抓一大把，也就是个人信息不一样而已。 关键要去找亮点，亮点啊，整个简历都跟流水线生产出来的一样。
点赞 评论 收藏
分享
12-24 12:19
牛客_产品运营部_运营
27届，从12月开始布局你的2026吧！
对于2027届应届毕业生来说，从现在12月开始准备2026年的校招是一个明智的选择。以下是一个详细的时间线和建议，希望能帮助27届uus更好地规划求职过程：2025年12月&nbsp;-&nbsp;2026年2月（寒假及寒假实习申请）自我评估：明确职业目标和个人优势，确定想要进入的行业和岗位类型。简历撰写：根据个人经历和技能，制作或更新一份专业的简历。确保简历简洁明了、重点突出。实习申请：寻找寒假实习机会，尤其是那些与未来职业方向相关的企业。寒假实习是积累经验的好时机。2026年3月&nbsp;-&nbsp;5月（暑期实习申请）技能提升：根据目标职位的要求，报名参加相关的培训课程或在线学习资源，如编程语言、数据分析工具等。模拟面试：...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 牛客2025仙途报告 #
14740次浏览 258人参与
# 实习要如何选择和准备？ #
130280次浏览 1509人参与
# 元旦假期你打算怎么过 #
1055次浏览 33人参与
# 你有哪些缓解焦虑的方法？ #
44622次浏览 868人参与
# 格力求职进展汇总 #
197800次浏览 1267人参与
# 实习没人带，苟住还是跑路？ #
547次浏览 18人参与
# 上班后和你想的一样吗？ #
95215次浏览 701人参与
# 双非本科的出路是什么？ #
189440次浏览 1500人参与
# 找工作，行业重要还是岗位重要？ #
87673次浏览 1751人参与
# 我们是不是被“优绩主义”绑架了？ #
1989次浏览 72人参与
# 今年你最想重开的一场面试是？ #
13441次浏览 144人参与
# 一人说一个提前实习的好处 #
24443次浏览 321人参与
# 机械人晒出你的简历 #
148543次浏览 885人参与
# vivo工作体验 #
35098次浏览 136人参与
# 你面试体验感最差/最好的公司 #
29900次浏览 493人参与
# 礼物开箱Plog #
3359次浏览 102人参与
# 牛友们的论文几号送审 #
63154次浏览 833人参与
# 秋招落幕，你是He or Be #
23165次浏览 395人参与
# 你觉得机械有必要实习吗？ #
16406次浏览 95人参与
# 机械只有读研才有出路吗？ #
30918次浏览 261人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务