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();
}
} 
