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