这次的题挺奇怪的。
大概是比较简单。。。也许吧？
$T1$暴力显然可过，就没什么可说的。
$T2$题目或者$std$锅了，好气啊本来能抢到两个绿框的。
不到三小时的时候先$AC$了一遍，结果发现自己的边界是错的（然而$std$也是错的）。
所以改成对的，然后就和$std$不一样了，然后就$WA$了。
$T3$一眼看着像$min25$筛然后就自闭了，尝试写然而并没有写出来。暴力跑路。
虽说$min25$的确应该可以过，但是正解简单得多，想复杂了。。。
T1：决战
大意：$n imes 3$的矩阵，每个棋子周围$8$个格子中的一些不能放置其它棋子。求放置$m$棋子的方案数。$n le 2500$
直接暴力$dp$。$O(n^2)$显然可过啊。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define mod 998244353 4 #define ri register int 5 void add(int&a,int b){a+=b;if(a>=mod)a-=mod;} 6 int dp[2][7501][8],ok[8],tr[8][8],n,m,ban[3][3],t[8][9]; 7 const int bit[]={0,1,1,2,1,2,2,3}; 8 int main(){ 9 ri n,m,ans=0; cin>>n>>m; 10 for(int i=0;i<3;++i)for(int j=0;j<3;++j)cin>>ban[i][j]; 11 if(ban[0][0]||ban[2][2])for(int i=0;i<8;++i)for(int j=0;j<8;++j)if(i>>1&j)tr[i][j]=1; 12 if(ban[0][2]||ban[2][0])for(int i=0;i<8;++i)for(int j=0;j<8;++j)if(j>>1&i)tr[i][j]=1; 13 if(ban[0][1]||ban[2][1])for(int i=0;i<8;++i)for(int j=0;j<8;++j)if(j&i)tr[i][j]=1; 14 if(ban[1][0]||ban[1][2])for(int i=0;i<8;++i)for(int j=0;j<8;++j)if(j>>1&j||i>>1&i)tr[i][j]=1; 15 for(int i=0;i<8;++i)for(int j=0;j<8;++j)if(!tr[i][j])t[i][++t[i][0]]=j; 16 dp[0][0][0]=1; ri mx=0,nw=1,nx=0,_=0,C=m-3*n-3; 17 while(nw^=1,nx^=1,C+=3,_++<n)for(ri i=0;i<8;++i)if(t[i][0])for(ri j=max(C,0);j<=m&&j<=_+_+_;++j)if(dp[nw][j][i]){ 18 for(ri k=t[i][0],g;g=t[i][k],k;--k)add(dp[nx][j+bit[g]][g],dp[nw][j][i]); 19 dp[nw][j][i]=0; 20 }for(ri i=0;i<8;++i)add(ans,dp[nw][m][i]); cout<<ans<<endl; 21 }
T2：gift
大意：$n$点，选有$A_i$代价，$x_i,y_i$同时选有$B_i$贡献。最大化$lfloor frac{sum B -1}{sum A} floor$。$n le 400,mle 10^5$
$01$分数规划+网络流。用那种$n$点$2m$边的写法。但是好像$n+m$点也能过。
千万不要处理$B$整除$A$的情况，不然会$WA$
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define S 2222222 5 #define s 4005 6 int n,m,c[s],e[s][s],w[S],fir[s],l[S],to[S],v[S],ec=1,tw[s],tot,d[s],q[s]; 7 bool bfs(){ 8 for(int i=1;i<=n+1;++i)d[i]=0; d[0]=1; 9 for(int h=1,t=1;h<=t;++h)for(int i=fir[q[h]];i;i=l[i])if(v[i]&&!d[to[i]]) 10 d[q[++t]=to[i]]=d[q[h]]+1; 11 return d[n+1]; 12 } 13 int dfs(int p,int f){ 14 if(p==n+1)return f; int r=f; 15 for(int i=fir[p];i&&r;i=l[i])if(d[to[i]]==d[p]+1&&v[i]){ 16 int x=dfs(to[i],min(v[i],r)); 17 if(!x)d[to[i]]=0; 18 v[i]-=x; v[i^1]+=x; r-=x; 19 }return f-r; 20 } 21 void link(int a,int b,int W){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;w[ec]=W;} 22 void con(int a,int b,int W){link(a,b,W);link(b,a,W);} 23 int main(){//freopen("0.in","r",stdin); 24 cin>>n>>m; 25 for(int i=1;i<=n;++i)scanf("%d",&c[i]),c[i]<<=1,con(0,i,0); 26 for(int i=1,x,y,W;i<=m;++i)scanf("%d%d%d",&x,&y,&W),e[x][y]+=W,e[y][x]+=W,tw[x]+=W,tw[y]+=W,tot+=W+W; 27 for(int i=1;i<=n;++i)for(int j=i+1;j<=n;++j)if(e[i][j])con(i,j,e[i][j]); 28 for(int i=1;i<=n;++i)tot-=e[i][i],tw[i]-=e[i][i]; 29 for(int i=1;i<=n;++i)link(i,n+1,tw[i]),link(n+1,i,0); 30 int l=0,r=700,md,Ans; 31 while(md=l+r>>1,l<=r){ 32 for(int i=2;i<=ec;++i)v[i]=w[i]; 33 ll ans=tot; 34 for(int i=1;i<=n;++i)if(md*c[i]-e[i][i]>=0)v[i<<1]=md*c[i]-e[i][i];else ans+=e[i][i]-md*c[i]; 35 while(bfs())ans-=dfs(0,0x7fffffff); 36 if(ans<=0)r=md-1;else l=Ans=md,l++; 37 }cout<<Ans<<endl; 38 }
T3：质数
大意：求$sumlimits_{i=1}^{n} 2^{f(i)}$。$f(i)$表示$i$的质因子种数。$ nle 10^{12} $
含义理解，$2^{f(i)}$可以理解为把所有质因子分成两个集合，同一种的所有次数出现在同一个集合中。
$2^{f(i)} = sumlimits_{j|i}[gcd(j,frac{i}{j})=1] = sumlimits_{j|i} sumlimits_{p|j,p|frac{i}{j}} mu(p)=sumlimits_{p=1} mu(p) sumlimits_{p^2|i}^{i le n} d(frac{i}{p^2}) $
$ans=sumlimits_{p=1}^{ sqrt{n} } mu(p) sumlimits_{i=1}^{frac{n}{p^2}} d(i)$
其中$sumlimits_{i=1}^{n} d(i) = sumlimits_{i=1}^{n} frac{n}{i}$
得到$ans=sumlimits_{p=1}^{sqrt{n}} mu(p) sumlimits_{i=1}^{frac{n}{p^2}} frac{n}{ip^2}$
整除分块。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define mod 998244353 4 #define S 2333333 5 #define ll long long 6 ll n;int ans,p[S],pc,np[S],mu[S]; 7 ll cal(ll n,int a=0){for(ll i=1,l,N;N=n/i,i<=n;i=l+1)l=n/N,a=(a+1ll*(l-i+1)*N)%mod;return a;} 8 int main(){ 9 cin>>n; int sq=sqrt(n); mu[1]=1; 10 for(int i=2;i<=sq;++i){ 11 if(!np[i])p[++pc]=i,mu[i]=-1;; 12 for(int j=1;i*p[j]<=sq;++j) 13 if(i%p[j])np[i*p[j]]=1,mu[i*p[j]]=-mu[i]; 14 else {np[i*p[j]]=1;break;} 15 } 16 for(int p=1;p<=sq;++p)ans=(ans+cal(n/p/p)*mu[p])%mod; 17 cout<<(ans+mod)%mod; 18 }