【題解+解題報告】2020浙江工業大學程式設計迎新賽——決賽（除了E和M以外）

寫在前面的話：
這次比賽的題目把我驚艷到了，題目質量非常高，給出題人點個贊！

A

知識點：模擬，
參考cf難度：1500
這道題其實讀懂題，按題意模擬就可以了，資料很小，所以每次操作直接排序即可，要注意的是每個學生能力值改變的時間點不要搞錯了，
復雜度： O ( n 2 l o g n ) O(n^2logn) O(n2logn)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct node{
    ll id,val,p;
};
node a[2000];
bool cmp(node a,node b){
    if(a.val!=b.val)return a.val>b.val;
    return a.id<b.id;
}
int main(){
    int t,i;
    int b;
    int n,r,l;
    cin>>n>>r>>l;
    for(i=0;i<n;i++)cin>>a[i].id;
    for(i=0;i<n;i++)cin>>a[i].val;
    for(i=0;i<n;i++)cin>>a[i].p;

    int len=n;
    while(len>1){
        sort(a,a+len,cmp);
        for(i=0;i<10;i++)a[i].val+=r;
        len=len/2+len%2;
        if(len==1)break;
        if(len>=6){
            for(i=0;i<3;i++)a[i].val-=l;
        }

        for(i=0;i<len;i++)a[i].val+=a[i].p;

    }
    cout<<a[0].id<<" "<<a[0].val;
}

B

知識點：狀壓搜索/DFS
參考cf難度：2100
第一次想到的演算法是貪心：列舉每個度數 i i i，先順時針到 i i i再逆時針；或者先逆時針到 i i i再順時針，結果wa了，甚至一度懷疑題目出問題了，
后面發現這個演算法是錯的，有可能出現先逆時針，再順時針，再逆時針的情況（因為每個點的 t t t是不同的，所以不能簡單的去貪心），正確做法是列舉每一次選擇順時針或者逆時針，這樣一共有 n n n次決策，總決策方案就是 2 n 2^n 2n種，
復雜度： O ( n ? 2 n ) O(n*2^n) O(n?2n)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
double xa,ya,xb,yb,xc,yc,xd,yd;
struct node{
    int w,v;
};
bool cmp(node a,node b){
    return a.w<b.w;
}
node a[22];
ll tong[361];
int main(){
    int t,i,j;
    int b;
    int n,r,l;
    int x,y;
    cin>>n>>x>>y;
    for(i=0;i<n;i++){
        ll w,v;
        cin>>w>>v;
        a[i].w=w;
        a[i].v=v;
        tong[w]=max(tong[w],v);
    }
    sort(a,a+n,cmp);
    ll mi=1e12;
    if(y<a[0].w){
        l=n-1,r=0;
    }
    else{
        for(i=0;i<n;i++){
            if(y<a[i].w)break;
        }
        l=i-1,r=i%n;
    }
  //  cout<<l<<" "<<r<<endl;
    for(i=0;i<1<<n;i++){
        int templ=l,tempr=r,st=y;
        ll p=i,sum=0,ma=0;
        for(j=0;j<n;j++){
            if(p&1){

                sum+=(st-a[templ].w+360)%360*x;
               // cout<<"1:"<<j<<" "<<(st-a[templ].w+360)%360*x<<endl;
                ma=max(ma,sum+a[templ].v);
                st=a[templ].w;
                templ=(templ-1+n)%n;

            }
            else{
                sum+=(a[tempr].w-st+360)%360*x;
             //   cout<<"2:"<<j<<" "<<(a[tempr].w-st+360)%360*x<<endl;
                ma=max(ma,sum+a[tempr].v);
                st=a[tempr].w;
                tempr=(tempr+1)%n;
            }
            p/=2;
        }
    //    cout<<"p"<<i<<" "<<sum<<endl;
        mi=min(mi,ma);
    }
    cout<<mi;

   // cout<<mi2<<endl;
}

C

知識點：前綴和預處理
參考cf難度：1600
這道題要求的是距離不大于k的所有01對的數量，那么對于每個0/1而言，只需要知道距離它不超過k的所有1/0的數量，然后前綴和預處理就可以O(1)查詢了，
復雜度：O(n)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll sum1[500020],sum2[500050];
int main(){
    int t,i;
    string s;
    ll n,c,k;
    cin>>k;
    cin>>s;
    n=s.length();
    ll s1=0,s2=0;
    for(i=0;i<s.length();i++){
        sum1[i+1]=s1+=s[i]=='0';
        sum2[i+1]=s2+=s[i]=='1';
    }
   // for(i=1;i<=n;i++)cout<<sum2[i]<<endl;
    ll cnt=0;
    for(i=0;i<s.length();i++){
        if(s[i]=='0'){
            cnt+=sum2[min(i+k+1,n)]-sum2[max(i-k,0LL)];
           // cout<<i<<" "<<min(i+k+1,n)<<" "<<max(i-k,0LL)<<endl;
        }
        else{
            cnt+=sum1[min(i+k+1,n)]-sum1[max(i-k,0LL)];
        }
       // cout<<cnt<<endl;
    }
    cout<<cnt/2;
}

D

知識點：貪心
參考cf難度：800
簽到題，很明顯當且僅當摸大魚體力不超過摸小魚兩倍的時候選擇摸大魚，否則一定會摸小魚，注意如果 n n n是奇數那么最后要用小魚補全，
復雜度 O ( T ) O(T) O(T)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll sum1[500020],sum2[500050];
int main(){
    int t,i;
    cin>>t;
    while(t--){
        ll n,a,b;
        cin>>n>>a>>b;
        if(a*2<=b)cout<<n*a<<endl;
        else cout<<n/2*b+n%2*a<<endl;
    }
}

F

知識點：計算幾何/（三分）
參考cf難度：1900
這道題官方題解非常優秀，不過我是用三分卡過去的，
當兩個點開始運動之后，很明顯距離是先變小、后變大這一程序，滿足可三分的性質，
由于double可能會卡精度，所以只要三分足夠多次就可以了，
復雜度: O ( T l o g ? ) O(Tlog?) O(Tlog?)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
double xa,ya,xb,yb,xc,yc,xd,yd;
double f(double k){
    double xf,yf;
    if(ya<yb)yf=ya+k;
    else yf=ya-k;
    if(xc<xd)xf=xc+k;
    else xf=xc-k;
    return sqrt((xf-xa)*(xf-xa)+(yf-yc)*(yf-yc));
}

int main(){
    int t,i;
    int b;
    int n,r,l;
    cin>>t;
    while(t--){

        cin>>xa>>ya>>xb>>yb>>xc>>yc>>xd>>yd;
        if(ya==yb){
            swap(xa,xc),swap(ya,yc),swap(xb,xd),swap(yb,yd);
        }
        double mi=sqrt((xc-xa)*(xc-xa)+(ya-yc)*(ya-yc));
        double len1=abs(yb-ya),len2=abs(xd-xc),cc=abs(len1-len2);
        if(len1<len2)xd-=cc;
        else yb-=cc;
    //    cout<<ya<<" "<<yb<<" "<<xc<<" "<<xd<<" "<<len1<<" "<<len2<<endl;
        double l=0,r=min(len1,len2);
        for(i=0;i<1000;i++){
            double lmid=l+(r-l)/3,rmid=l+2*(r-l)/3;
            if(f(lmid)<f(rmid))r=rmid;
            else l=lmid;
        }

        printf("%.2f\n",f(l));
    }
}

G

知識點：概率論
參考cf難度：1300
看到資料范圍這么小，直接套期望的公式就可以了：
E = ∑ i = 1 n p ( i ) ? i E=\sum_{i=1}^n p(i)*i E=∑i=1n?p(i)?i
其中 p ( i ) p(i) p(i)用古典概型的條件概率直接求就可以，
復雜度： O ( n ) O(n) O(n)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll sum1[500020],sum2[500050];
int main(){
    int t,i;
    int a,b;
    cin>>a>>b;
    double sum=a+b;
    double p=0,res=0,sump=0;
    for(i=1;i<=a+1;i++){
        p=(1-sump)*b/sum;
        sump+=p;
        res+=i*p;
        sum--;
    }
    printf("%.6f",res);
}

H

知識點：貪心
參考cf難度：1500
這道題其實很簡單，不過由于讀題勸退所以前2h居然沒有一發提交hhh
題目的公式已經告訴你了，那么可以根據每個怪的屬性求出最大的傷害，然后求出擊殺次數，之后按次數從小到大選擇就可以模擬了，
不過這道題出的不好的一點的是居然存在血量為0的怪，理論上無視它就可以了（
復雜度： O ( T n l o g n ) O(Tnlogn) O(Tnlogn)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll vis[1000100],prime[1000100],x=0,tong[1000100];
struct node{
    int hp,d,val;
};
node a[100022];
bool cmp(node a,node b){
    return a.val<b.val;
}
int main(){
//    init();
    int t,i,j;
   // for(i=999990;i<=1000000;i++)cout<<i<<" "<<tong[i]<<endl;
   // return 0;
    int b;
    int n,r,l,m;

    cin>>t;
    while(t--){
        ll sum=0;
        cin>>n>>m;
        int c1,k1,c2,k2;
        cin>>c1>>k1>>c2>>k2;
        for(i=0;i<n;i++)cin>>a[i].hp;
        for(i=0;i<n;i++)cin>>a[i].d;
        for(i=0;i<n;i++){

            int dmg=max(0,max(c1-k1*a[i].d,c2-k2*a[i].d));
            if(dmg==0){a[i].val=1e9;continue;}
          //  cout<<dmg<<endl;
            a[i].val=a[i].hp/dmg+(a[i].hp%dmg!=0);
        }
        sort(a,a+n,cmp);

        for(i=0;i<n&&sum+a[i].val<=m;i++)sum+=a[i].val;
        cout<<i<<endl;
    }

}

I

知識點：思維
參考cf難度：1400
非常巧妙的一道題，這道題的關鍵就是構造出（或者猜出） n ≥ 2 n≥2 n≥2時最小面積一定是1，
具體的構造方法參考下圖：
復雜度： O ( T ) O(T) O(T)

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int main(){
    int t,i;
    int b;
    int n,r,l;
    cin>>t;
    while(t--){
        double x;
        cin>>x;
        if(x==1)cout<<"0.5"<<endl;
       else  printf("%.1f\n",1.0);
    }
}

J

知識點：dp、貪心
參考cf難度：2200
非常好的一道題，題意大概這樣：將每個1變成0的條件是：這個1的前面都沒有0，并且變完了之后會把這個1前面 k k k個字符都變成1，
因此可以得到dp方程：
d p [ i ] = 1 + ∑ j = 1 k d p [ i ? j ] dp[i]=1+\sum_{j=1}^kdp[i-j] dp[i]=1+∑j=1k?dp[i?j]
這個方程可以簡化成這樣：
前 k k k項dp項之和與 d p [ i ? 1 ] dp[i-1] dp[i?1]也可以建立某種聯系，經過推導后可以得出：
d p [ i ] = 2 ? d p [ i ? 1 ] ? d p [ i ? k ? 1 ] dp[i]=2*dp[i-1]-dp[i-k-1] dp[i]=2?dp[i?1]?dp[i?k?1]
有 t t t次交換的機會，很明顯的，一定優先交換右邊的1，因為右邊的1會帶來更多的次數，
之后將預處理出的dp陣列進行求和就可以了，
復雜度: O ( n + t ) O(n+t) O(n+t)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int mod=1e9+7;
ll power(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
ll inv(ll x){
    return power(x,mod-2);
}
struct node{
    int l,r;
};
ll dp[100010];
int main(){
//    init();
   //cout<<inv(2)<<endl;
    int t,i,j,k;
   // for(i=999990;i<=1000000;i++)cout<<i<<" "<<tong[i]<<endl;
   // return 0;
    int b;
    int n,r,l,m;
    int x,y;
    cin>>n>>k>>t;
    string s;
    cin>>s;
    dp[1]=1;
    for(i=2;i<=k+1;i++){
        dp[i]=dp[i-1]*2%mod;
    }
    for(i=k+2;i<=1e5;i++){
        dp[i]=2*dp[i-1];
        if(i>k+1)dp[i]-=dp[i-k-1];
        dp[i]=(dp[i]+mod)%mod;
    }
    //for(i=1;i<=10;i++)cout<<dp[i]<<" ";
    while(t){
        for(i=s.length()-1;i>=0;i--){
            if(s[i]=='1')break;
        }
        for(;i>=0;i--)if(s[i]=='0')break;
        if(i<0)break;
        for(;i<s.length()-1;i++){
            if(s[i+1]=='1')swap(s[i],s[i+1]),t--;
            if(!t)break;
        }
        if(!t)break;
    }
    ll sum=0;
    for(i=0;i<s.length();i++){
        sum+=(s[i]=='1')*dp[i+1];
        sum%=mod;
    }
    cout<<sum;

}

K

知識點：博弈
參考cf難度：1300
當n小于3時，顯然后手勝，
n≥3時，一定先手勝，證明如下：
若n為奇數，第一次這樣畫：
后面每次對方怎么畫，自己在對稱的另一邊畫同樣的形狀即可，
若n為偶數，第一次這樣畫：

然后用同樣的方式，對稱著畫，保證每次畫完都是軸對稱狀態，這樣第一次無法畫的一定是對方，
復雜度： O ( T ) O(T) O(T)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll sum1[500020],sum2[500050];
int main(){
    int t,i;
    cin>>t;
    while(t--){
        ll n,a,b;
        cin>>n;
        if(n<3)cout<<"Hugin\n";
        else cout<<"Steve\n";
    }
}

L

知識點：數論，構造演算法
參考cf難度：1900
初始序列為1,2,3……n，第一次某個數加1，第二次某個數加2，以此類推，求運算元最小的次數使得gcd大于1，并輸出字典序最小的序列，
首先可以證明，最小的運算元為n-1，證明如下：
必要性：
若n是2的倍數，那么把所有數變成2的倍數需要n-1次，若n不是2的倍數，則需要n次，
若n%3=0，那么把所有數變成3的倍數需要n-1次，若n%3=1，那么無論如果不能讓他們都變成3的倍數，若n%3=2，那么把所有數變成3的倍數需要n次，
一般地，若我們要讓所有數的gcd變成p，首先要讓1,…,p-1所有數變成p的倍數，然后遇到一個p的時候操作在模p意義下是無效的，所以至少需要n-1次，
充分性：
設有1,2…n的初始序列，我們讓1加到n-1，2加到n-2……以此類推，n-1加到1上面，這樣n-1次操作所有數都變成n了，
證明完畢，
所以這道題的關鍵是怎么找到字典序最小的n-1的序列，
假設我們要讓所有數的gcd變成p，我們可以讓1加到p-1上，2加到p-2上……p-1加到1上，這次第一個數變成p了，可以再讓他加p（這樣字典序最小）；之后讓p+1加到2p-1上……以此類推，最終我們的序列是p-1,p-2…1,1,2p-1,2p-2…p+1,1,3p-1…
那么如果讓字典序最小，很明顯就是讓p最小，而p又必須是n的因子（這樣才能n-1次操作完成），所以這道題只要求出n除了1以外最小的因子就可以了，這個操作可以通過線性篩進行預處理，
復雜度 O ( n ) O(n) O(n)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll vis[1000100],prime[1000100],x=0,tong[1000100];
void init(){
    ll n=1e6,i,j;
    for(i=2;i<=n;i++)
    {
        if(!vis[i]) prime[x++]=i;
        for(j=0;j<x;j++)
        {
            if(i*prime[j]>n) break;
            vis[i*prime[j]]=true;
            tong[i*prime[j]]=prime[j];
            if(i%prime[j]==0) break;
        }
    }

}
int main(){
    init();
    int t,i,j;
   // for(i=999990;i<=1000000;i++)cout<<i<<" "<<tong[i]<<endl;
   // return 0;
    int b;
    int n,r,l;
    cin>>t;
    while(t--){
        scanf("%d",&n);
        int p=tong[n];
        if(p==0)p=n;
       // if()
        if(n==1)printf("1\n1\n");
        else{
            printf("%d\n",n-1);
            for(i=p;i<=n;i+=p){
                for(j=i-1;j>i-p;j--){
                    if(!(i==p&&j==i-1))printf(" ");
                    printf("%d",j);
                }
                if(i!=n)printf(" 1");
            }
            printf("\n");
        }


    }
}