Introduction
It's very difficult. I'm aware of the gap in knowledge points again
Knowledge points involved
Shape pressure DP, thinking, combinatorial mathematics, DSU on Tree, line segment tree
Link: 2019 Nanchang Regional
subject
C
Give a large nonnegative integer n n n. Calculate integer pairs that meet the following conditions ( i , j ) (i,j) (i,j), n n n is given in binary form
- 0 ≤ j ≤ i ≤ n 0\le j\le i\le n 0≤j≤i≤n
- i & n = i i \&n=i i&n=i
- i & j = 0 i\& j=0 i&j=0
Train of thought: it is constructed according to the problem setting conditions i i i only in n n The 1 bit of n corresponds to a value, and j j j is not greater than i i Under the premise of i, the value of each bit is arbitrary, in order to ensure i i i greater than j j j. In construction i i i is constructed in sequence from low to high. Assuming that the current bit of i is fixed to 1 and the other high bits are fixed to 0, discuss the low bit by category, that is, similar to 000001xxxxx, assuming that it is the penultimate p p p-bit, n n n this bit corresponds to 1, reciprocal 1 − p 1-p 1 − p bit in total k k k 1, m m m zeros, then the total number of schemes can be obtained as:
C
k
0
2
m
+
k
+
C
k
1
2
m
+
k
−
1
+
⋯
+
C
k
k
2
m
C_k^02^{m+k}+C_k^12^{m+k-1}+\dots+C_k^k2^m
Ck02m+k+Ck12m+k−1+⋯+Ckk2m
=
2
m
(
C
k
0
2
k
+
C
k
1
2
k
−
1
+
⋯
+
C
k
k
)
=2^m(C_k^02^k+C_k^12^{k-1}+\dots+C_k^k)
=2m(Ck02k+Ck12k−1+⋯+Ckk)
=
2
m
(
C
k
k
2
k
+
C
k
k
−
1
2
k
−
1
+
⋯
+
C
k
0
2
0
)
=2^m(C_k^k2^k+C_k^{k-1}2^{k-1}+\dots+C_k^02^0)
=2m(Ckk2k+Ckk−12k−1+⋯+Ck020)
Therefore, the formula can be deduced, but obviously the formula is more complex and can be further simplified
Known
(
1
+
x
)
n
=
C
n
0
x
0
+
C
n
1
x
1
+
...
C
n
n
x
n
(1+x)^n=C_n^0x^0+C_n^1x^1+\dots C_n^nx^n
(1+x)n=Cn0x0+Cn1x1+...Cnnxn
take
x
=
2
x=2
x=2
(
1
+
2
)
n
=
C
n
0
2
0
+
C
n
1
2
1
+
...
C
n
n
2
n
(1+2)^n=C_n^02^0+C_n^12^1+\dots C_n^n2^n
(1+2)n=Cn020+Cn121+...Cnn2n
Therefore, the final formula can be deduced as 2 m 3 k 2^m3^k 2m3k
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;//Plus i=j=0
printf("%lld\n",res);
}
return 0;
}
E
General idea of the title: give a n n Undirected graph of n nodes, with m m m weighted edges, each of which is either black or white. Now we need to select some edges to construct a new graph so that the graph is connected, and we can only select no more than k k k white edges, find the sum of the maximum edge weights that can be obtained by the new graph. If the new graph cannot be connected, output - 1
Idea: first select all the black edges, then mark them with the union search set, then sort the white edges from large to small, traverse the white edges, select the white edges on the premise of ensuring connectivity, and select the white edges with large edge weight if there are more times
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 edge needs to be entered
e[++cnt].from=u;
e[cnt].to=v;
e[cnt].w=w;
} else {//Direct use of black edges
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 the white edges and ensure connectivity first
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
Main idea of the title: omitted
Idea: first of all, the module given in the topic is a composite number, and the maximum prime factor is 2803. Then, the factorial corresponding to the value greater than 2803 will inevitably result in 0. Only the numbers in the range of 1 ~ 2803 need to be considered, so only violence is needed O ( n 2 ) O(n^2) O(n2) traverse all intervals, judge the maximum value that can be reached by different interval sizes, and finally find the corresponding answer according to the input (note that the larger the interval is, the larger the value will be)
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 factorial
mul[i]=(mul[i-1]*i)%mod;
for(int i=1; i<=n; i++) {
int x;
scanf("%lld",&x);
a[i]=mul[x];//Record results
}
for(int i=1; i<=n; i++)
if(a[i]) {//Re record results
res[++cnt].val=a[i];
res[cnt].id=i;
sum[cnt]=sum[cnt-1]+res[cnt].val%mod;//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
Main idea of the title: Yes n n n football teams take part in the game, and each team will compete with the rest n − 1 n-1 n − 1 team will play one game each. Now the results of all games will be given to judge whether there is a champion. If there is an output number, otherwise the corresponding string will be output. The winner of each game will get 3 points and each draw will get 1 point. The champion is the team with the largest score and the largest number of net goals (net goals = goals - goals lost)
Idea: directly count the violence, and finally rank according to the requirements of the topic and give a special judgment 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, which doesn't affect it
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;
}