C

Yet Another Array Restoration

给定两个元素x和y，及项数n，求最大元素最小的等差数列。思路：让公差d尽量的小，然后从x和y中较大的一个不断-d枚举，若项数不到n，继续从较大元素不断+d枚举。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx = 1e6 + 10;int t,n,x,y;
int main()
{cin>>t;while(t--){cin>>n>>x>>y;int ma=max(x,y);int mi=min(x,y);int d;for(int i=n-1;i>=1;i--){if((ma-mi)%i==0){d=(ma-mi)/i;break;}}if(ma-d*n>0){cout<<ma;for(int i=1;i<n;i++){cout<<' '<<ma-d*i;}cout<<'\n';}else{int cnt=1;cout<<ma;int i=1;while(cnt<n){if(ma-i*d>0){cout<<' '<<ma-i*d;i++;cnt++;}else break;}i=1;while(cnt<n){cout<<' '<<ma+i*d;i++;cnt++;}cout<<'\n';}}// system("pause");
}

D

Minimum Product

给定a,b及它们的下界x,y。n次减一操作后使得a*b最小，一开始以为是让较小元素尽量小，结果最后一个样例过不了。正确的思路是：两个各自减最多，多余就减另一个。

a能到的最小值是max(x,a−n)

b能到的最小值是max(y,b−n)比较一下,那个小就优先对谁操作,剩下就对另一个数操作。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx = 1e6 + 10;
int t;
ll a,b,x,y,n;
int main()
{cin>>t;while(t--){cin>>a>>b>>x>>y>>n;//mi=min(a,b);int q=max(x,a-n),w=max(y,b-n);if(q<=w){int tem=n-(a-q);b=max(y,b-tem);cout<<q*b<<'\n';}else{int tem=n-(b-w);a=max(x,a-tem);cout<<a*w<<'\n';}}system("pause");
}

 

M

Colorful Candies

求在定区间长度下不同数的个数，思路：使用map记录每个数出现的次数，区间外的数出现次数不断减减，当某个数出现次数为0时，在map中删掉，当i>=k时不断统计map.size

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx = 3e5 + 10;
map<int,int>m;
int n,k;
int a[maxx];
int main()
{cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i];int ans=-0x3f3f3f3f,tem=0;for(int i=1;i<=n;i++){m[a[i]]++;if(i>=k){tem=m.size();ans=max(ans,tem);m[a[i-k+1]]--;if(m[a[i-k+1]]==0) m.erase(a[i-k+1]);}}cout<<ans<<'\n';system("pause");
}

N

取石子游戏

威佐夫博弈

结论：非奇异局势，先手必胜，否则先手必败

奇异局势的状态公式:

                                   ak = [ k * (1 + √5) / 2 ]     ,   ([x]表示对x取整，也就是 (int)x )

                                   bk = ak + k

#include <iostream>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxx = 1e6 + 10;
int n,m;
int main()
{while(cin>>n>>m){int a=min(n,m);int b=max(n,m);double k=(double)b-a;int tem=(int)(k*(1+sqrt(5.0))/2.0);if(a==tem) cout<<0<<'\n';else cout<<1<<'\n';}system("pause");
}