ZAFU_2021_1_24_2021寒假個人賽第一場題解

題目的解法不一定唯一，這里給出我自己個人過題時使用的解法，

A題
原題鏈接:https://codeforces.com/problemset/problem/1370/A
相關tag:規律總結

我們要選擇兩個不同的數，使得他們的最大公約數盡可能大，
假設我們已經找到了第一個數為x，那么第二個數選擇x的整數倍的話，他們的最大公約數都是x，
但是題目已經說了必須選兩個不同的數，因此我們選擇x和2x，此時最大公約數為x，

2x要滿足小于等于n，因此x的最大值就是n/2

#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

int main()
{
    IOS
    int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        cout<<n/2<<endl;
    }
}

B題
原題鏈接:https://codeforces.com/problemset/problem/1027/A
相關tag:規律總結

每個字符都必須要變換一次，
那位置對稱的兩個字符必須只能是原本就相同，或者ASCII碼相差2，一個+1一個-1變成相同的，
for一遍判斷是否都滿足即可，

#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

int main()
{
    IOS
    int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        string s;cin>>s;
        bool f=1;
        for(int i=0;i*2<n;i++)
            if(s[i]!=s[n-i-1]&&abs(s[i]-s[n-i-1])!=2) {f=0;break;}
        if(f) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}

C題
原題鏈接:https://codeforces.com/problemset/problem/1027/B
相關tag:規律總結

我們把橫縱坐標加起來等于偶數的點歸類為第一類點，橫縱坐標加起來是奇數的歸類為第二類點，
我們可以先算出第一類點總共有base個
然后根據行標和列標去找當前這個點是從上到下從左到右第幾個該類點，如果是第二類點，再加上base個，

接下來是如何計算當前位置是從上到下從左到右第幾個點，
注意到第一行里面有a=(n+1)/2個第一類點，那么第一行里第二類點的個數就是b=n-a個點，
而第二行會變為b個第一類點，a個第二類點
第三行會變為a個第一類點，b個第二類點
…

我們要算第x行第y列是從上到下從左到右第幾個點，
第x行這一行，第y列是這一行的第(y+1)/2個點，
前面的x-1行，其中的(x-1)/2對奇偶行可以組成一組，每組有a+b個點，
當(x-1)是奇數的時候，額外加上第x-1行有幾個點，視情況加上a或者b，

上述三個加起來便是答案(第二類點多加個base），

#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

int main()
{
    IOS
    ll n,q;
    cin>>n>>q;
    ll base=n*n/2+(n%2?1:0);//第一類點共有多少個
    ll a=(n+1)/2,b=n-a;//a代表第一行的第一類點有多少個，b代表第一行的第二類點有多少個
    while(q--)
    {
        ll x,y;cin>>x>>y;
        ll temp=x+y,out=(y+1)/2+(x-1)/2*(a+b);
        //out為輸出的答案，前面的(x-1)/2是兩行兩行的對數，每對有a+b個點,而(y+1)/2是第x行的點的個數
        if(temp%2)//如果是第二類點
        {
            out+=base;//值需要加上第一類點的個數
            if(x%2==0) out+=b;//如果x是偶數，前面的x-1行還剩下一行的第二類點未計算，加上對應個數b
        }
        else if(x%2==0) out+=a;//第一類點;如果x是偶數，前面的x-1行還剩下第x-1行的第一類點未計算，加上對應個數a
        cout<<out<<endl;
    }
}

D題
原題鏈接:https://codeforces.com/problemset/problem/1285/B
相關tag:規律總結

假設存在一個區間[l,r]，這些值加起來不小于總共的n個數加起來，
那么對于左側的區間[1,l-1]和[r+1,n]這兩個區間的和x和y，滿足x+y<=0，
實際上當x和y出現一個小于等于0的時候，另一側取到盡頭，那么另一個累加和就是0了，必然存在滿足條件的區間，

所以直接從左到右和從右到左for兩遍算總和，如果出現了小于等于0的值，那就是NO，

#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

int num[100000+7];

int main()
{
    IOS
    int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        for(int i=0;i<n;i++) cin>>num[i];
        bool flag=1;
        ll sum=0;
        for(int i=0;i+1<n;i++)
        {
            sum+=num[i];
            if(sum<=0) flag=0;
        }
        sum=0;
        for(int i=n-1;i>0;i--)
        {
            sum+=num[i];
            if(sum<=0) flag=0;
        }
        if(flag) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}

E題
原題鏈接:https://codeforces.com/problemset/problem/1027/C
相關tag:數學，結論

我們要構造一個矩形，那么必定是選擇兩組長度一樣的木棒，
另這兩根木棒的長度各為a和b，
周長T=a+b,而面積S=a × \times × b
注意到T × \times ×T/S就等于2+(a/b+b/a)
我們要使得a/b+b/a最小，注意到這是個對勾函式，當a和b比值最接近的時候取到最小，

因此我們先對所有木棒排個序，再找到所有長度相同的有哪些，比較長度最接近的即可，

#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

int main()
{
    IOS
    int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        vector<int>num(n);
        for(int i=0;i<n;i++) cin>>num[i];
        sort(num.begin(),num.end());
        vector<int>data;//有哪些長度相等的一對木棒
        for(int i=0;i+1<n;i++)
        {
            if(num[i]==num[i+1])//第i根和第i+1根湊成一對
            {
                data.push_back(num[i]);
                i++;
            }
        }
        int tar=0;
        for(int i=1;i+1<data.size();i++)
        {
            if(data[tar+1]*data[i]>data[tar]*data[i+1]) tar=i;//轉換成乘法，避免了乘法運算，找到data[i]/data[i+1]最小的位置
        }
        cout<<data[tar]<<' '<<data[tar]<<' '<<data[tar+1]<<' '<<data[tar+1]<<endl;
    }
}

F題
原題鏈接:https://codeforces.com/problemset/problem/817/C
相關tag:二分

對于整數x，我們把它十進制各位加起來的值記為temp，
注意到x的值每+1，由于十進制存在進位，temp的值可能+1，也可能減少，
也就是說x和temp的差值，隨著x的增大，只可能越變越大，不會越來越小，

滿足二分的條件，二分去找不滿足的最大的值為多少，用n減去它就是滿足的個數了，

#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

ll change(ll x)
{
    ll ret=0;
    while(x)
    {
        ret+=x%10;
        x/=10;
    }
    return ret;
}

int main()
{
    IOS
    ll n,s;cin>>n>>s;
    ll l=0,r=n;
    while(l<r)
    {
        ll mid=(l+r)/2+1;
        if(mid-change(mid)>=s) r=mid-1;
        else l=mid;
    }
    cout<<n-l<<endl;
}