A.方格游戏
仔细看题！！！这题就是一个大分类讨论
140行让我给调出来了。。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod=1000000007;
const int inv2=500000004;
const int inv3=333333336;
int sum1(int x,int y){return 1ll*(x+y)*(y-x+1)%mod*inv2%mod;}
int S(int x){return 1ll*x*(x+1)%mod*(2*x+1)%mod*inv2%mod*inv3%mod;}
int sum2(int x,int y){return (S(y)-S(x-1)+mod)%mod;}
int i,j,k,n,m,x,y,t,p,ans;
int S1[100010],S2[100010];
struct matrix{int u,d,l,r;}M[100010];
int calc1(int n,int m){
int ret1=1ll*n*m%mod*m%mod*sum1(0,n-1)%mod-1ll*m*m%mod*sum2(0,n-1)%mod;
if (ret1<0)ret1+=mod;
int ret2=1ll*n*m%mod*n%mod*sum1(0,m-1)%mod-1ll*n*n%mod*sum2(0,m-1)%mod;
if (ret2<0)ret2+=mod;
return (ret1+ret2)%mod;
}
bool cmp1(const matrix &a,const matrix &b){
return a.l<b.l;
}
bool cmp2(const matrix &a,const matrix &b){
return a.u<b.u;
}
int main(){
scanf("%d%d%d",&n,&m,&p);
for (i=1;i<=p;i++)scanf("%d%d%d%d",&M[i].u,&M[i].d,&M[i].l,&M[i].r);
ans=calc1(n,m);
// printf("1----%d\n",ans);
//-----ok-----
for (i=1;i<=p;i++){
int s1,s2;
s1=1ll*m*(M[i].r-M[i].l+1)%mod;
s2=((sum2(M[i].u,M[i].d)-1ll*(n+1)*sum1(M[i].u,M[i].d)%mod)%mod
+1ll*n*(n+1)%mod*inv2%mod*(M[i].d-M[i].u+1)%mod)%mod;
ans=(ans-1ll*s1*s2%mod)%mod;
if (ans<0)ans+=mod;
// printf("1.5---->%d\n",ans);
s1=1ll*n*(M[i].d-M[i].u+1)%mod;
s2=((sum2(M[i].l,M[i].r)-1ll*(m+1)*sum1(M[i].l,M[i].r)%mod)%mod
+1ll*m*(m+1)%mod*inv2%mod*(M[i].r-M[i].l+1)%mod)%mod;
ans=(ans-1ll*s1*s2%mod)%mod;
if (ans<0)ans+=mod;
}
for (i=1;i<=p;i++)ans=(ans+calc1(M[i].d-M[i].u+1,M[i].r-M[i].l+1))%mod;
// printf("2----%d\n",ans);
sort(M+1,M+1+p,cmp1);
for (i=1;i<=p;i++)S1[i]=(S1[i-1]+1ll*(M[i].d-M[i].u+1)*(M[i].r-M[i].l+1)%mod)%mod;
for (i=p;i>=1;i--)S2[i]=(S2[i+1]+1ll*(M[i].d-M[i].u+1)*(M[i].r-M[i].l+1)%mod)%mod;
int cnt1=0;
for (i=2;i<=p;i++){
int s1,s2,s3,ret;
s1=1ll*(M[i].r-M[i].l+1)*inv2%mod;
s2=1ll*(M[i].l+M[i].r)*(M[i-1].r-M[i-1].l+1)%mod;
s3=2ll*sum1(M[i-1].l,M[i-1].r)%mod;
ret=1ll*s1*(s2-s3)%mod*(M[i-1].d-M[i-1].u+1)%mod*(M[i].d-M[i].u+1)%mod;
ret=(ret+1ll*S1[i-2]*sum1(M[i].l-M[i-1].l,M[i].r-M[i-1].l)%mod*(M[i].d-M[i].u+1)%mod)%mod;
if (i!=p){
ret=(ret+1ll*S2[i+1]*S1[i-2]%mod*(M[i].l-M[i-1].l)%mod)%mod;
ret=(ret+1ll*S2[i+1]*sum1(M[i].l-M[i-1].r,M[i].l-M[i-1].l)%mod*(M[i-1].d-M[i-1].u+1)%mod)%mod;
}
// printf("ret:%d\n",ret);
ans=(ans+ret)%mod;
}
// printf("2.5----%d\n",ans);
sort(M+1,M+1+p,cmp2);
for (i=1;i<=p;i++)S1[i]=(S1[i-1]+1ll*(M[i].d-M[i].u+1)*(M[i].r-M[i].l+1)%mod)%mod;
for (i=p;i>=1;i--)S2[i]=(S2[i+1]+1ll*(M[i].d-M[i].u+1)*(M[i].r-M[i].l+1)%mod)%mod;
int cnt2=0;
for (i=2;i<=p;i++){
int s1,s2,s3,ret;
s1=1ll*(M[i].d-M[i].u+1)*inv2%mod;
s2=1ll*(M[i].u+M[i].d)*(M[i-1].d-M[i-1].u+1)%mod;
s3=2ll*sum1(M[i-1].u,M[i-1].d)%mod;
ret=1ll*s1*(s2-s3)%mod*(M[i-1].r-M[i-1].l+1)%mod*(M[i].r-M[i].l+1)%mod;
// printf("ret0.5:%d\n",ret);
ret=(ret+1ll*S1[i-2]*sum1(M[i].u-M[i-1].u,M[i].d-M[i-1].u)%mod*(M[i].r-M[i].l+1)%mod)%mod;
if (i!=p){
ret=(ret+1ll*S2[i+1]*S1[i-2]%mod*(M[i].u-M[i-1].u)%mod)%mod;
ret=(ret+1ll*S2[i+1]*sum1(M[i].u-M[i-1].d,M[i].u-M[i-1].u)%mod*(M[i-1].r-M[i-1].l+1)%mod)%mod;
}
// printf("ret:%d\n",ret);
ans=(ans+ret)%mod;
}
// printf("3----%d\n",ans);
for (i=1;i<=p;i++){
int RET=0,RET1=0,RET2=0,RET3=0,ret1,ret2,ret3;
//RET1:2lx~lx+rx
//RET2:lx+rx+1~2*rx
//RET3:|i2-i1|
//-------part1
ret1=sum2((M[i].l+M[i].l)%mod,(M[i].l+M[i].r)%mod);
ret2=1ll*(3-4ll*M[i].l%mod)
*sum1((M[i].l+M[i].l)%mod,(M[i].l+M[i].r)%mod)%mod;
ret3=1ll*(M[i].r-M[i].l+1)
*(4ll*M[i].l%mod*M[i].l%mod-6ll*M[i].l%mod+2)%mod;
RET1=((ret1+ret2)%mod+ret3)%mod;
// printf("RET1:%d\n",RET1);
if (RET1<0)RET1+=mod;
ret1=sum2((M[i].l+M[i].r+1)%mod,(M[i].r+M[i].r)%mod);
ret2=1ll*(4ll*M[i].r%mod+3)%mod
*sum1((M[i].l+M[i].r+1)%mod,(M[i].r+M[i].r)%mod)%mod;
ret3=1ll*(M[i].r-M[i].l)*(M[i].r+M[i].r+2)%mod*(1+2*M[i].r)%mod;
RET2=((ret1-ret2)%mod+ret3)%mod;
// printf("RET2:%d\n",RET2);
if (RET2<0)RET2+=mod;
RET3=2ll
*(1ll*(M[i].r-M[i].l+1)*sum1(1,M[i].r-M[i].l)%mod
-sum2(1,M[i].r-M[i].l))%mod;
if (RET3<0)RET3+=mod;
// printf("RET3:%d\n",RET3);
RET=(RET1+RET2-RET3)%mod;if (RET<0)RET+=mod;
ans=(ans+1ll*RET*(M[i].u-1)%mod*(n-M[i].d)%mod)%mod;
//--------part2
ret1=sum2((M[i].u+M[i].u)%mod,(M[i].u+M[i].d)%mod);
ret2=1ll*(3-4ll*M[i].u%mod)
*sum1((M[i].u+M[i].u)%mod,(M[i].u+M[i].d)%mod)%mod;
ret3=1ll*(M[i].d-M[i].u+1)
*(4ll*M[i].u%mod*M[i].u%mod-6ll*M[i].u%mod+2)%mod;
RET1=((ret1+ret2)%mod+ret3)%mod;
if (RET1<0)RET1+=mod;
ret1=sum2((M[i].u+M[i].d+1)%mod,(M[i].d+M[i].d)%mod);
ret2=1ll*(4ll*M[i].d%mod+3)%mod
*sum1((M[i].u+M[i].d+1)%mod,(M[i].d+M[i].d)%mod)%mod;
ret3=1ll*(M[i].d-M[i].u)*(M[i].d+M[i].d+2)%mod*(1+2*M[i].d)%mod;
RET2=((ret1-ret2)%mod+ret3)%mod;
if (RET2<0)RET2+=mod;
RET3=2ll
*(1ll*(M[i].d-M[i].u+1)*sum1(1,M[i].d-M[i].u)%mod
-sum2(1,M[i].d-M[i].u))%mod;
if (RET3<0)RET3+=mod;
RET=(RET1+RET2-RET3)%mod;if (RET<0)RET+=mod;
ans=(ans+1ll*RET*(M[i].l-1)%mod*(m-M[i].r)%mod)%mod;
}
if (ans<0)ans+=mod;
printf("%d\n",ans);
return 0;
}B.切切糕
有趣的博弈论。
考虑从小到大切，让对手为难。。。
考虑n=1,m=1时，直接把一个糕平均分成两块
我们可以联想到最佳的时候应该是无论用不用优先权最后结果应该是一样的
然后DP
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int i,j,k,n,m,x,y,t;
int a[5010];
double f[5010][5010];
bool cmp(int a,int b){return a>b;}
int main(){
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+1+n,cmp);
for (i=1;i<=n;i++)f[i][0]=f[i-1][0]+a[i];
for (i=1;i<=n;i++)
for (j=1;j<=min(i,m);j++){
double x=(f[i-1][min(j,i-1)]-f[i-1][j-1]+a[i])/2.0;
if (x<0.0)f[i][j]=a[i]+f[i-1][min(i-1,j)];else f[i][j]=x+f[i-1][j-1];
}
printf("%.6lf\n",f[n][m]);
return 0;
}E.区间矩阵乘法
嘛坑点在题目没有直接告诉你d<=sqrt(n)。。。。
求sqrt(n)个前缀和什么的就行了
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=200010;
int i,j,k,n,m,x,y,t,d,p1,p2;
unsigned int p[N],sum[N][450],a[N];
int main(){
scanf("%d",&n);
for (i=1;i<=n;i++)scanf("%d",&a[i]);
for (i=1;i<=n;i++)p[i]=p[i-1]+a[i];
int s=sqrt(n);
for (i=1;i<=s;i++){
for (j=1;j<=n;j++)
sum[j][i]=sum[max(0,j-i)][i]+a[j];
}
scanf("%d",&m);
while (m--){
scanf("%d%d%d",&d,&p1,&p2);
unsigned int ans=0;
for (j=0;j<=d-1;j++)
ans+=(p[p2+d*j+d-1]-p[p2+d*j-1])*(sum[p1+d*(d-1)+j][d]-sum[max(0,p1+j-d)][d]);
printf("%u\n",ans);
}
return 0;
}F.棋盘
一开始想成网络流了。。。
其实比较麻烦的是两列只有一种填法且列号差为奇数的情况
考虑黑白染色，从上往下填黑，从下往上填白，尽量多填白格就行了
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int i,j,k,n,m,x,y,t;
int ans[310][310];
int a[310],b[310];
bool check(int x,int y){
if (ans[x][y]||ans[x-1][y]||ans[x][y-1]||ans[x][y+1]||ans[x+1][y])return 0;
return 1;
}
int color(int x,int y){return (x^y)&1;}
int main(){
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++){
scanf("%d",&a[i]);
if (a[i]>(n+1)/2){printf("No\n");return 0;}
}
if (n%2==0){
for (j=1;j<=m;j++)
for (i=1;i<=n;i++)
if (a[j]&&check(i,j)){a[j]--;ans[i][j]=1;}
}
else{
for (j=1;j<=m;j++)
if (a[j]==(n+1)/2){
b[++b[0]]=j;
for (i=1;i<=n;i++)
if (check(i,j)&&a[j]){
ans[i][j]=1;a[j]--;
}
}
for (j=b[1]-1;j>=1;j--){
for (i=1;i<=n;i++)
if (check(i,j)&&a[j]){
ans[i][j]=1;a[j]--;
}
}
for (k=1;k<b[0];k++){
if ((b[k+1]-b[k])%2==0){
for (j=b[k]+1;j<b[k+1];j++)
for (i=1;i<=n;i++)
if (a[j]&&check(i,j)){
ans[i][j]=1;a[j]--;
}
}
else{
for (j=b[k]+1;j<b[k+1];j++){
int t=0;
for (i=n;i>=1;i--)
if (check(i,j)&&color(i,j-b[k])==0&&a[j]){
ans[i][j]=1;a[j]--;t++;
}
for (i=1;i<=n;i++)
if (check(i,j)&&color(i,j-b[k])==1&&a[j]){
ans[i][j]=1;a[j]--;
}
}
}
}
for (j=b[b[0]]+1;j<=m;j++)
for (i=1;i<=n;i++)
if (check(i,j)&&a[j]){
ans[i][j]=1;a[j]--;
}
for (j=1;j<=m;j++)if (a[j]){printf("No\n");return 0;}
}
printf("Yes\n");
for (i=1;i<=n;i++){
for (j=1;j<=m;j++)printf("%d",ans[i][j]);
printf("\n");
}
return 0;
}G.密集子图
一道普普通通的状压DP。。。
点分成三类讨论，按照BFS顺序更新。。。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int f[15][600000];
int w[15][15];
const int mod=998244353;
int mi(int x,int y){
if (y==0)return 1;
int t=mi(x,y>>1);
t=1ll*t*t%mod;
if (y&1)t=1ll*t*x%mod;
return t;
}
int i,j,k,n,m,x,y,t,p,q,K;
int id1[15],id2[15],ID[15],M[15];
bool check(int x){
for (int i=1;i<=n;i++,x/=3)
if (x%3==0)return 0;
return 1;
}
int main(){
scanf("%d%d",&n,&K);
M[0]=1;for (i=1;i<=12;i++)M[i]=3*M[i-1];
for (i=1;i<=n*(n-1);i++){
scanf("%d%d%d%d",&x,&y,&p,&q);
w[x][y]=1ll*p*mi(q,mod-2)%mod;
}
int NUM=mi(3,n);f[0][2]=1;p=q=0;
for (i=0;i<K;i++)
for (int P=0;P<NUM;P++)
if (f[i][P]){
y=P;id1[0]=0;id2[0]=0;x=0;memset(ID,0,sizeof ID);
for (q=1;q<=n;q++,y/=3)
if (y%3==2)id1[++id1[0]]=q,ID[q]=1;
else if (y%3==1)id2[++id2[0]]=q,ID[q]=1;
else if (y%3==0)x=x+(1<<(q-1));
for (j=x;j;j=(j-1)&x){
y=j;p=1;int ww=0;
for (q=1;q<=n;q++,y>>=1){
int W;
if (!(y&1)){ww=ww+ID[q]*M[q-1];continue;}
ww=ww+2*M[q-1];
W=1;for (k=1;k<=id1[0];k++)W=1ll*W*(1-w[id1[k]][q])%mod;p=1ll*p*(1-W)%mod;
W=1;for (k=1;k<=id2[0];k++)W=1ll*W*(1-w[id2[k]][q])%mod;p=1ll*p*W%mod;
if (p<0)p+=mod;
}
f[i+1][ww]=(f[i+1][ww]+1ll*f[i][P]*p%mod)%mod;
}
}
int ans=0;
for (i=0;i<=K;i++)
for (j=0;j<NUM;j++)
if (check(j)&&f[i][j]){
ans=(ans+f[i][j])%mod;
}
printf("%d\n",ans);
return 0;
}H.线段树
就先处理左右两个子树自己内部的贡献，再处理左子树对右子树的贡献和右子树对左子树的贡献，记忆化搜索即可。
#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int T;
long long n;
const int mod=1000000007;
struct data{
long long sumL,sumR;
int mark;
long long ans;
};
map<long long,data>mp;
void dfs(long long n){
if (mp[n].mark)return;
mp[n].mark=1;
long long R=n>>1,L=n-R;
dfs(L);dfs(R);
mp[n].ans=(mp[L].ans+mp[R].ans+1)%mod;
mp[n].ans=(mp[n].ans+1ll*mp[L].sumR*(R%mod)%mod)%mod;
mp[n].ans=(mp[n].ans+1ll*mp[R].sumL*(L%mod)%mod)%mod;
mp[n].sumL=(mp[L].sumL+mp[R].sumL)%mod;mp[n].sumL=(mp[n].sumL+R%mod)%mod;
mp[n].sumR=(mp[L].sumR+mp[R].sumR)%mod;mp[n].sumR=(mp[n].sumR+L%mod)%mod;
mp[n].ans=(mp[n].ans+n-2)%mod;
return ;
}
int main(){
scanf("%d",&T);
mp[1].mark=1;mp[1].ans=1;
while (T--){
scanf("%lld",&n);
dfs(n);
printf("%lld\n",mp[n].ans);
}
return 0;
}J.合法序列
暴力枚举前(1<<k)位，然后DP
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod=998244353;
int i,j,k,n,m,x,y,t;
int f[510][16],a[16],ans;
int main(){
scanf("%d%d",&n,&k);
for (int p=0;p<(1<<(1<<k));p++){
t=p;int flag=0;
for (i=0;i<(1<<k);i++)a[i]=t&1,t>>=1;
for (i=0;i<=(1<<k)-k;i++){
t=0;for (j=i;j<=i+k-1;j++)t=t*2+a[j];
if (a[t]==0){
flag=1;break;
}
}
if (flag)continue;
memset(f,0,sizeof f);
t=0;for (j=(1<<k)-k;j<=(1<<k)-1;j++)t=t*2+a[j];
f[(1<<k)-1][t]=1;
for (i=(1<<k);i<n;i++)
for (j=0;j<(1<<k);j++){
if (f[i-1][j]){
for (int num=0;num<=1;num++){
t=((j<<1)&((1<<k)-1))+num;
if (a[t])f[i][t]=(f[i][t]+f[i-1][j])%mod;
}
}
}
for (i=0;i<(1<<k);i++)ans=(ans+f[n-1][i])%mod;
}
printf("%d\n",ans);
return 0;
}K.独立
注意输入的是随机数据！！！
反正就是找环然后暴力枚举选还是不选
注意环上的点不要多加！！！
#include <map>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100010;
const int q=101;
const int b=137;
const int p=1000000007;
int i,j,k,n,m,x,y,t,w[N],B[N];
int a[N],c[N],fi[N],ne[N],la[N];
int s[N],cir[N],ins[N];
map<pair<int,int>,int>mp;
long long f[N][2],ans;
void add(int x,int y,int t){
k++;a[k]=y;c[k]=t;
if (fi[x]==0)fi[x]=k;else ne[la[x]]=k;
la[x]=k;
}
void dfs1(int x,int fa){
B[x]=1;s[++s[0]]=x;ins[x]=1;
for (int i=fi[x];i;i=ne[i])
if (a[i]!=fa){
if (ins[a[i]]==1&&B[a[i]]==1){
B[a[i]]=2;
cir[++cir[0]]=a[i];
}
else if (!B[a[i]]){
dfs1(a[i],x);
}
}
ins[x]=0;
}
long long DP(int x,int fa){
B[x]=3;f[x][0]=0;f[x][1]=w[x];
for (int i=fi[x];i;i=ne[i])
if (a[i]!=fa){
if (B[a[i]]==1)DP(a[i],x);
f[x][0]+=max(f[a[i]][0],f[a[i]][1]);
f[x][1]+=max(f[a[i]][0],f[a[i]][1]-c[i]);
}
return max(f[x][0],f[x][1]);
}
long long work(int x){
s[0]=0;cir[0]=0;
dfs1(x,-1);
long long mx=0;
for (int P=0;P<(1<<cir[0]);P++){
int t=P;long long tmp=0;
for (int i=1;i<=s[0];i++)if (B[s[i]]==3)B[s[i]]=1;
for (int i=1;i<=cir[0];i++){
int u=t&1;t>>=1;
if (u==0){
f[cir[i]][0]=0;f[cir[i]][1]=-(1ll<<60);
}
else{
f[cir[i]][0]=-(1ll<<60);f[cir[i]][1]=0;tmp+=w[cir[i]];
}
}
for (int i=1;i<=s[0];i++)if (B[s[i]]==1)tmp+=DP(s[i],-1);
mx=max(mx,tmp);
}
return mx;
}
int main(){
scanf("%d%d%d%d%d%d",&n,&m,&x,&y,&w[0],&t);
for (i=1;i<=n;i++)w[i]=(1ll*q*w[i-1]%p+b)%p;
for (i=1;i<=m;i++){
x=(1ll*x*q%p+b)%p;y=(1ll*y*q%p+b)%p;t=(1ll*t*q%p+b)%p;
int xx=x%n+1,yy=y%n+1;
if (xx>yy)swap(xx,yy);
if (xx!=yy&&!mp[make_pair(xx,yy)]){
mp[make_pair(xx,yy)]=1;
add(xx,yy,t);
add(yy,xx,t);
}
}
for (i=1;i<=n;i++)if (B[i]==0)ans+=work(i);
printf("%lld\n",ans);
return 0;
}M.自白书
都不好意思说这是一道题。。。
#include <cstdio>
using namespace std;
int main() {
printf("kecheng");
}
Comments | NOTHING