20191102 「HZOJ NOIP2019 Round #12」20191102模拟
先开坑。
md原题写挂我也真是。。。
100+20+10
白夜
打表大法吼
显然，不在环上的点对答案的贡献是 \((k-cycle)^{k-1}\) 。
打表得到环上的递推式，矩阵一下乘起来就好了。
#include<bits/stdc++.h>
using namespace std;
#define int long long
template <typename Tp>
void read(Tp &x){
x=0;char ch=1;int fh;
while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
if(ch=='-') ch=getchar(),fh=-1;
else fh=1;
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
x*=fh;
}
const int maxn=100007;
const int maxm=200007;
const int mod=998244353;
int n,T;
int Head[maxn],to[maxm],Next[maxm],tot=1;
int aa,bb,k;
bool vis[maxn];
int col[maxn];
int size[maxn],top[maxn],dep[maxn],fa[maxn];
int son[maxn];
void add(int x,int y){
to[++tot]=y,Next[tot]=Head[x],Head[x]=tot;
}
namespace baoli{
bool check(int x){
vis[x]=1;
for(int i=Head[x];i;i=Next[i]){
int y=to[i];
if(col[y]==col[x]) return false;
if(vis[y]) continue;
bool tmp=check(y);
if(tmp==false) return false;
}
if(x==aa){
if(col[aa]==col[bb]) return false;
if(!vis[bb]){
bool tmp=check(bb);
if(tmp==false) return false;
}
}
if(x==bb){
if(col[aa]==col[bb]) return false;
if(!vis[aa]){
bool tmp=check(aa);
if(tmp==false) return false;
}
}
return true;
}
int dfs(int step){
if(step==n+1){
memset(vis,0,sizeof(vis));
if(check(1)) return 1;
else return 0;
}
int res=0;
for(int i=1;i<=k;i++){
col[step]=i;
res=(res+dfs(step+1))%mod;
}
return res;
}
void MAIN(){
while(T--){
read(aa);read(bb);read(k);
if(k==1&&n!=1){
puts("0");continue;
}
printf("%lld\n",dfs(1));
}
}
}
namespace Try{
struct Matrix{
int mat[4][4],n;
Matrix(){
memset(mat,0,sizeof(mat));
n=2;
}
void reset(){
for(int i=1;i<=n;i++) mat[i][i]=1;
}
};
Matrix Mul(Matrix a,Matrix b){
Matrix c;c.n=a.n;
int l=a.n;
for(int i=1;i<=l;i++){
for(int j=1;j<=l;j++){
for(int k=1;k<=l;k++){
c.mat[i][j]+=(a.mat[i][k]*b.mat[k][j]%mod);
c.mat[i][j]%=mod;
}
}
}
return c;
}
Matrix fpow(Matrix x,int p){
Matrix res;res.reset();
while(p){
if(p&1) res=Mul(res,x);p>>=1;
x=Mul(x,x);
}
return res;
}
int ksm(int x,int p){
int res=1;
while(p){
if(p&1) res=res*x%mod;p>>=1;
x=x*x%mod;
}
return res;
}
void dfs1(int x,int f,int dp){
dep[x]=dp,fa[x]=f,size[x]=1;
int mx=-1;
for(int i=Head[x];i;i=Next[i]){
int y=to[i];
if(y==f) continue;
dfs1(y,x,dp+1);
size[x]+=size[y];
if(size[y]>mx) son[x]=y,mx=size[y];
}
}
void dfs2(int x,int tp){
top[x]=tp;
if(!son[x]) return;
dfs2(son[x],tp);
for(int i=Head[x];i;i=Next[i]){
int y=to[i];
if(y==son[x]||y==fa[x]) continue;
dfs2(y,y);
}
}
int lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
return x;
}
int calc(int cyc){
if(cyc==1) return 0;
if(cyc==2){
return k*(k-1)%mod;
}
Matrix base,ans;
base.mat[1][1]=k-2,base.mat[1][2]=k-1,base.mat[2][1]=1;
ans.mat[1][1]=k*(k-1)%mod;
ans=Mul(ans,fpow(base,cyc-2));
return ans.mat[1][1];
}
void MAIN(){
dfs1(1,0,1);dfs2(1,1);
int x,y,ans=0;
while(T--){
read(x);read(y);read(k);
int lc=lca(x,y);int cyc=dep[x]+dep[y]-2*dep[lc]+1;
ans=ksm(k-1,n-cyc);
ans=(ans*calc(cyc))%mod;
printf("%lld\n",ans);
}
}
}
signed main(){
freopen("night.in","r",stdin);freopen("night.out","w",stdout);
read(n);
for(int x,i=2;i<=n;i++){
read(x);
add(x,i);add(i,x);
}
read(T);
Try::MAIN();
fclose(stdin);fclose(stdout);
return 0;
}光明
区间最大字段和
GSS系列
样例太弱了...
这题被 \(O(n^2)\) 氧化钙过去了。。。
订正后代码：
using namespace std;
template <typename Tp>
void read(Tp &x){
x=0;char ch=1;int fh;
while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
if(ch=='-') ch=getchar(),fh=-1;
else fh=1;
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
x*=fh;
}
const int maxn=100007;
int n,T;
int w[maxn];
int xx[maxn],yy[maxn];
#define lfc (x<<1)
#define rgc ((x<<1)|1)
#define mid ((l+r)>>1)
struct node{
int sum,lf,rg,val;
};
int sum[maxn<<2],val[maxn<<2],rg[maxn<<2],lf[maxn<<2];
void pushup(int x){
sum[x]=sum[lfc]+sum[rgc];
lf[x]=max(lf[lfc],sum[lfc]+lf[rgc]);
rg[x]=max(rg[rgc],sum[rgc]+rg[lfc]);
val[x]=max(max(val[lfc],val[rgc]),lf[rgc]+rg[lfc]);
}
void build(int x,int l,int r){
if(l==r){
int fff=1;
if(xx[l]%2==1&&yy[l]%2==1) fff=-1;
val[x]=sum[x]=lf[x]=rg[x]=fff*w[l];return;
}
build(lfc,l,mid);build(rgc,mid+1,r);
pushup(x);
}
int L,R,need;
node query(int x,int l,int r){
if(L<=l&&r<=R) return (node){sum[x],lf[x],rg[x],val[x]};
if(L>mid) return query(rgc,mid+1,r);
if(R<=mid) return query(lfc,l,mid);
node res,a1=query(lfc,l,mid),a2=query(rgc,mid+1,r);
res.sum=a1.sum+a2.sum;
res.lf=max(a1.lf,a1.sum+a2.lf);
res.rg=max(a2.rg,a1.rg+a2.sum);
res.val=max(max(a1.val,a2.val),a1.rg+a2.lf);
return res;
}
void change_val(int x,int l,int r){
if(l==r){
int fff=1;
if(xx[l]%2==1&&yy[l]%2==1) fff=-1;
val[x]=sum[x]=lf[x]=rg[x]=fff*need;
return;
}
if(L<=mid) change_val(lfc,l,mid);
else change_val(rgc,mid+1,r);
pushup(x);
}
int fffff;
void change_qf(int x,int l,int r){
if(l==r){
sum[x]=lf[x]=rg[x]=val[x]=-w[l]*fffff;
return;
}
if(L<=mid) change_qf(lfc,l,mid);
else change_qf(rgc,mid+1,r);
pushup(x);
}
void cz1(){
int a,b;
read(L);read(a);read(b);
if(a%2==1&&b%2==1){fffff=1;
change_qf(1,1,n);}
else{
fffff=-1;
change_qf(1,1,n);
}
xx[L]=a,yy[L]=b;
}
void cz2(){
read(L);read(need);
change_val(1,1,n);
w[L]=need;
}
void cz3(){
read(L);read(R);
printf("%d\n",query(1,1,n).val);
}
int main(){
freopen("light.in","r",stdin);freopen("light.out","w",stdout);
read(n);
for(int i=1;i<=n;i++) read(w[i]);
for(int i=1;i<=n;i++){
read(xx[i]);read(yy[i]);
}
build(1,1,n);
read(T);int op;
while(T--){
read(op);
if(op==1) cz1();
if(op==2) cz2();
if(op==3) cz3();
}
return 0;
}暗雪
区间Dp+四边形不等式优化
这题数据被 \(O(n^4)\) 氧化钙过去了。
#include<bits/stdc++.h>
using namespace std;
#define int long long
template <typename Tp>
void read(Tp &x){
x=0;char ch=1;int fh;
while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
if(ch=='-') ch=getchar(),fh=-1;
else fh=1;
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
x*=fh;
}
const int maxn=407;
const int INF=1e18;
int n,kk,a[maxn];
int dp[maxn][maxn][maxn];
int opt[maxn][maxn],s[maxn];
void Init(){
read(n);read(kk);
if(kk<=9&&(1<<kk)<n){
puts("-1");exit(0);
}
for(int i=1;i<=n;i++){
read(a[i]);
}
}
void Work(){
sort(a+1,a+n+1);
for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
if(i==j) dp[i][j][0]=0;
else dp[i][j][0]=INF;
}
}
for(int k=1;k<=kk;k++){
for(int i=1;i<=n;i++) opt[i][i]=i;
for(int len=2;len<=n;len++){
for(int l=1;l+len-1<=n;l++){
int r=l+len-1;
dp[l][r][k]=INF;
for(int p=opt[l][r-1];p<=opt[l+1][r];p++){
if(p+1>r) continue;
int val=dp[l][p][k-1]+dp[p+1][r][k-1]+s[r]-s[l-1];
if(val<dp[l][r][k]){
dp[l][r][k]=val;opt[l][r]=p;
}
}
}
}
}
int div=__gcd(dp[1][n][kk],s[n]);
printf("%lld/%lld\n",dp[1][n][kk]/div,s[n]/div);
}
signed main(){
freopen("snow.in","r",stdin);freopen("snow.out","w",stdout);
Init();
Work();
return 0;
}
