导语

难度很大，再一次意识到了知识点上的差距

涉及的知识点

状压DP，思维，组合数学，DSU on Tree，线段树

链接：2019 Nanchang Regional

题目

C

题目大意：给出一个很大的非负整数$n$，计算满足下列条件的整数对$(i,j)$的个数，$n$以二进制方式给出

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

思路：根据题设条件，构造出来的$i$只能在$n$的1位上对应有值，而$j$在不大于$i$的前提下，每一位的取值时随意的，为了保证$i$大于$j$，在构造$i$的时候，从低位到高位依次构造，假设i的当前位固定为1，其余高位固定为0，分类讨论低位的情况，即类似000001xxxxx的情况，假设当前是倒数第$p$位，$n$该位对应为1，倒数$1-p$位共$k$个1，$m$个0，那么总方案数可以得到为：

$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)$

因此可以推得公式，但显然公式较为复杂，还可以进一步简化

已知$(1+x{)}^n=C_n^0{x}^0+C_n^1{x}^1+\dots C_n^n{x}^n$
将$x=2$带入得
$(1+2{)}^n=C_n^0{2}^0+C_n^1{2}^1+\dots C_n^n{2}^n$

因此可以推得最终的公式为$2^m{3}^k$

代码

#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;//加上i=j=0printf("%lld\n",res);}return 0;
}

E

题目大意：给出一个$n$个节点的无向图，有$m$条有权边，每条边非黑即白，现在要从中选择一些边构造新图，使得图连通，并且只能选择不超过$k$条白边，求出新图能获得的最大边权之和，如果无法使新图连通，输出-1

思路：首先将所有的黑边选中，然后用并查集标记，接着按照从大到小排序白边，遍历白边，在确保连通的前提下选取白边，如果还有多的次数，就选择边权大的白边

代码

#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) {//路径压缩if(x==f[x])return x;return f[x]=Seek(f[x]);
}
void Union(int x,int y) {//合并int fx=Seek(x),fy=Seek(y);if(fx!=fy)f[fx]=fy;
}
struct node {//重载比大小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));//初始化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) {//白边需要录入e[++cnt].from=u;e[cnt].to=v;e[cnt].w=w;} else {//黑边直接采用if(Seek(u)!=Seek(v))Union(u,v);sum+=w;}}sort(e+1,e+1+cnt);//排序for(int i=1; i<=cnt&&k; i++) {//遍历所有的白边，首先保证连通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

题目大意：略

思路：首先，题目给的模数是一个合数，最大质因数为2803，那么，大于2803的值对应的阶乘就必然结果为0，只需要考虑1 ~ 2803这个范围内的数字即可，那么只需要暴力$O(n^2)$遍历所有的区间，判断不同的区间大小能到达的最大值是多少即可，最后再根据输入找到对应的答案（注意，区间越大，所得到的值必然也就越大）

代码

#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++)//预处理阶乘mul[i]=(mul[i-1]*i)%mod;for(int i=1; i<=n; i++) {int x;scanf("%lld",&x);a[i]=mul[x];//记录结果}for(int i=1; i<=n; i++)if(a[i]) {//重新记录结果res[++cnt].val=a[i];res[cnt].id=i;sum[cnt]=sum[cnt-1]+res[cnt].val%mod;//前缀和}for(int i=1; i<=cnt; i++)for(int j=i; j<=cnt; j++)//尝试不同的区间范围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

题目大意：有$n$支足球队参加比赛，每只队伍会和其余$n-1$队各比赛一场，现在给出所有比赛的结果，判断是否有冠军，如果有输出编号否则输出对应字符串，每场比赛胜者得3分，平局各得1分，冠军是分数最大且净进球数最多的队伍（净进球数=进球数-丢球数）

思路：直接暴力统计即可，最后根据题目要求排序并特判1

代码

#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++)//这里其实算重了，但是相对大小不变，不影响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;
}

参考文献

1. 2019ICPC南昌 C And and Pair dp（二项式定理 / dp）
2. 2019 ICPC 南昌区域赛 - G Eating Plan（技巧+暴力）