2019 Nanchang (relive the classic)

Introduction

It's very difficult. , Once again aware of the gap in knowledge points

Knowledge points involved

Pressure DP, thinking , Combinatorial mathematics ,DSU on Tree, Line segment tree

link ：2019 Nanchang Regional

subject

C

The main idea of the topic ： Give a large nonnegative integer $n$, Calculate integer pairs that meet the following conditions $(i,j)$ The number of ,$n$ Given in binary

1. $0\le j\le i\le n$
2. $i\&n=i$
3. $i\&j=0$

Ideas ： Set the conditions according to the questions , Constructed $i$ Only in $n$ Of 1 There is a value corresponding to the bit , and $j$ No more than $i$ Under the premise of , The value of each bit is arbitrary , In order to ensure $i$ Greater than $j$, In the structure $i$ When , From low to high structures , hypothesis i The current bit of is fixed to 1, Other high positions are fixed as 0, Classify and discuss the low order situation , It's like 000001xxxxx The situation of , Suppose it is the penultimate $p$ position ,$n$ This bit corresponds to 1, Reciprocal $1-p$ All in all $k$ individual 1,$m$ individual 0, Then the total number of schemes can be obtained as ：

$C_k^0{2}^{m+k}+C_k^1{2}^{m+k-1}+\cdots +C_k^k{2}^m$
$=2^m(C_k^0{2}^k+C_k^1{2}^{k-1}+\cdots +C_k^k)$
$=2^m(C_k^k{2}^k+C_k^{k-1}{2}^{k-1}+\cdots +C_k^0{2}^0)$

So we can deduce the formula , But obviously the formula is more complicated , It can be further simplified

It is known that $(1+x{)}^n=C_n^0{x}^0+C_n^1{x}^1+\dots C_n^n{x}^n$
take $x=2$ Brought in
$(1+2{)}^n=C_n^0{2}^0+C_n^1{2}^1+\dots C_n^n{2}^n$

Therefore, the final formula can be deduced as $2^m{3}^k$

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define int long long
using namespace std;
const int maxn=1e5+5;
const int mod=1e9+7;
int T;
char s[maxn];
int qpow(int power,int base) {
    
    int result=1;
    while(power) {
    
        if(power&1)
            result=result*base%mod;
        power>>=1;
        base=base*base%mod;
    }
    return result%mod;
}
signed main() {
    
    scanf("%lld",&T);
    while(T--) {
    
        scanf("%s",s+1);
        int len=strlen(s+1),cnt=0,res=0;
        for(int i=len; i>=1; i--)
            if(s[i]=='1') {
    
                res=(res+(qpow(cnt,3)*qpow(len-i-cnt,2))%mod)%mod;
                cnt++;
            }
        res=(res+1)%mod;// add i=j=0
        printf("%lld\n",res);
    }
    return 0;
}

E

The main idea of the topic ： Give a $n$ An undirected graph of nodes , Yes $m$ Right edge , Each side is either black or white , Now select some edges from them to construct a new graph , Make the graph connected , And you can only choose no more than $k$ White edge , Find the maximum sum of edge weights that can be obtained by the new graph , If the new graph cannot be connected , Output -1

Ideas ： First select all the black edges , Then use the union search mark , Then sort the white edges from large to small , Traverse the white edge , Select the white edge on the premise of ensuring connectivity , If there are more times , Choose the white edge with large edge weight

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define int long long
using namespace std;
const int maxn=5e5+5;
int T,n,m,k,f[maxn];
bool vis[maxn];
int Seek(int x) {
    // Path compression 
    if(x==f[x])return x;
    return f[x]=Seek(f[x]);
}
void Union(int x,int y) {
    // Merge 
    int fx=Seek(x),fy=Seek(y);
    if(fx!=fy)f[fx]=fy;
}
struct node {
    // Overload ratio size 
    int from,to,w;
    bool operator<(const node &a)const {
    
        return w>a.w;
    }
} e[maxn];
signed main() {
    
    scanf("%lld",&T);
    while(T--) {
    
        scanf("%lld%lld%lld",&n,&m,&k);
        memset(vis,0,sizeof(vis));// initialization 
        int sum=0,cnt=0;
        bool flag=0;
        for(int i=1; i<=n; i++)f[i]=i;
        while(m--) {
    
            int u,v,w,c;
            scanf("%lld%lld%lld%lld",&u,&v,&w,&c);
            if(c) {
    // White edges need to be entered 
                e[++cnt].from=u;
                e[cnt].to=v;
                e[cnt].w=w;
            } else {
    // The black edge is directly used 
                if(Seek(u)!=Seek(v))
                    Union(u,v);
                sum+=w;
            }
        }
        sort(e+1,e+1+cnt);// Sort 
        for(int i=1; i<=cnt&&k; i++) {
    // Traverse all white edges , First, ensure connectivity 
            int u=e[i].from,v=e[i].to;
            if(Seek(u)!=Seek(v)) {
    
                Union(u,v);
                k--;
                sum+=e[i].w;
                vis[i]=1;
            }
        }
        for(int i=1; i<=n; i++)
            if(Seek(i)!=Seek(1)) {
    
                flag=1;
                break;
            }
        if(flag) {
    
            printf("-1\n");
            continue;
        }
        for(int i=1; i<=cnt&&k; i++)
            if(vis[i])continue;
            else {
    
                k--;
                sum+=e[i].w;
            }
        printf("%lld\n",sum);
    }
    return 0;
}

G

The main idea of the topic ： A little

Ideas ： First , The module given by the topic is a composite number , The maximum prime factor is 2803, that , Greater than 2803 The factorial corresponding to the value of is bound to result in 0, Just think about it 1 ~ 2803 The number in this range is enough , Then just violence $O(n^2)$ Traverse all the intervals , Judge the maximum value that can be reached by different interval sizes , Finally, find the corresponding answer according to the input （ Be careful , The larger the range , The value obtained must be larger ）

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define int long long
using namespace std;
const int maxn=1e5+5;
const int mod=998857459;
int n,m,a[maxn],mul[maxn]= {
    1},cnt,sum[3000],ans[maxn];
struct node {
    
    int val,id;
} res[3000];
signed main() {
    
    scanf("%lld%lld",&n,&m);
    for(int i=1; i<2803; i++)// Preprocessing factorials 
        mul[i]=(mul[i-1]*i)%mod;
    for(int i=1; i<=n; i++) {
    
        int x;
        scanf("%lld",&x);
        a[i]=mul[x];// Records of the results 
    }
    for(int i=1; i<=n; i++)
        if(a[i]) {
    // Re record the results 
            res[++cnt].val=a[i];
            res[cnt].id=i;
            sum[cnt]=sum[cnt-1]+res[cnt].val%mod;// The prefix and 
        }
    for(int i=1; i<=cnt; i++)
        for(int j=i; j<=cnt; j++)// Try different ranges 
            ans[res[j].id-res[i].id+1]=max(ans[res[j].id-res[i].id+1],(sum[j]-sum[i-1]+mod)%mod);
    while(m--) {
    
        int x,len=INF;
        scanf("%lld",&x);
        for(int i=1; i<=n; i++)
            if(ans[i]>=x) {
    
                len=i;
                break;
            }
        if(len==INF)printf("-1\n");
        else printf("%lld\n",len);
    }
    return 0;
}

L

The main idea of the topic ： Yes $n$ A football team takes part in the match , Each team will compete with the rest $n-1$ Each team has a match , Now give the results of all competitions , Judge whether there is a champion , If there is an output number, otherwise the corresponding string is output , The winner of every game gets 3 branch , Each side gets a draw 1 branch , The champion is the team with the largest score and the largest number of net goals （ Net goals = goals - Number of balls lost ）

Ideas ： Direct violence statistics , Finally, sort and judge according to the requirements of the topic 1

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define int long long
using namespace std;
const int maxn=1e3+50;
int n,match[121][121];
struct node {
    
    int get,score,id;
    bool operator<(const node& a)const {
    
        if(score==a.score)return get>a.get;
        return score>a.score;
    }
} team[121];
signed main() {
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >>n;
    for(int i=1; i<=n; i++) {
    
        for(int j=1; j<=n; j++)
            cin >>match[i][j];
        team[i].id=i;
    }
    if(n==1) {
    
        cout <<1;
        return 0;
    }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)// It's actually heavy here , But the relative size remains the same , No effect 
            if(i!=j) {
    
                team[i].get+=match[i][j];
                team[i].get-=match[j][i];
                team[j].get+=match[j][i];
                team[j].get-=match[i][j];
                if(match[i][j]>match[j][i])team[i].score+=3;
                else if(match[i][j]==match[j][i])team[i].score++,team[j].score++;
                else team[j].score+=3;
            }
    sort(team+1,team+1+n);
    if(team[1].score==team[2].score&&team[1].get==team[2].get)cout <<"play-offs";
    else cout <<team[1].id;
    return 0;
}

reference

1. 2019ICPC nanchang C And and Pair dp（ binomial theorem / dp）
2. 2019 ICPC Nanchang regional race - G Eating Plan（ skill + violence ）