由于本人NOIP2023做的太烂了，被教练拉去做NOIP2022了qwq
first hour:这t1看上去还行，先写了
second hour:t2看上去有些难度，让我想一想
third hour:快想出来了，先写一写吧
fourth hour:写写写写写.....
最后100pts遗憾离场......
赛后有了深刻的认识，很多题是不能一步到位的，只能拼暴力。
P8865 [NOIP2022] 种花
预处理+前缀和即可。
本人代码自带大常数，写的非常史。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 998244353
#define mxn 1010
ll n,m,c,f,T,id,ans1,ans2,cnt1,cnt2;
ll nexti[mxn][mxn],nextj[mxn][mxn];
char s[mxn][mxn];
void solve(){
cin>>n>>m>>c>>f;
memset(nexti,0,sizeof(nexti));
memset(nextj,0,sizeof(nextj));
ans1=ans2=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
nexti[i][j]=n+1,nextj[i][j]=m+1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>s[i][j];
if(s[i][j]=='1'){
nexti[i][j]=i,nextj[i][j]=j;
for(int k=i-1;k;k--){
if(s[k][j]=='0')nexti[k][j]=i;
else break;
}
for(int k=j-1;k;k--){
if(s[i][k]=='0')nextj[i][k]=j;
else break;
}
}
}
}
for(int i=1;i<m;i++){
for(int j=1;j<=n;){
if(s[j][i]=='1'){
j++;continue;
}
cnt1=0,cnt2=0;
for(int k=j+2;k<nexti[j][i];k++)
cnt1+=nextj[k][i]-i-1,cnt2+=(nextj[k][i]-i-1)*(nexti[j][i]-k-1);
for(int k=j;k<nexti[j][i]-2;k++){
ans1=(ans1+(nextj[k][i]-i-1)*cnt1%mod)%mod;
ans2=(ans2+(nextj[k][i]-i-1)*cnt2%mod)%mod;
cnt1-=nextj[k+2][i]-i-1;
cnt2-=(nextj[k+2][i]-i-1)*(nexti[j][i]-k-3);
}
j=nexti[j][i]+1;
}
}
cout<<ans1*c<<' '<<ans2*f<<'\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>T>>id;while(T--)solve();
return 0;
}
P8866 [NOIP2022] 喵了个喵
较难的思维好题。
\(k=2\times n-2\) 的情况是送的。
\(k=2\times n-1\) 的情况考虑离线，对于多出来的数分类讨论。
具体可以看这篇题解，讲的非常牛逼。
另外就是这题细节及其多，要维护的东西及其多，再加上万恶的spj，更加深其史的程度。
#include<bits/stdc++.h>
using namespace std;
#define mxn 1010
#define mxm 2000010
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
int T,n,m,k,crd[mxm],empt;
int id[mxn];
vector<pii> ans;
deque<int> sta[mxn];
queue<int> q;
void init(){
while(!q.empty())q.pop();
for(int i=1;i<=n;i++)sta[i].clear();
for(int i=1;i<n;i++)q.push(i),q.push(i);
memset(id,0,sizeof(id));
ans.clear(),empt=n;
}
bool _push(int x){
if(!id[x]){
if(q.empty())return 0;
int u=q.front();q.pop();
sta[u].pb(x),id[x]=u;
ans.pb(mp(u,0));
}
else{
int u=id[x];
q.push(u),id[x]=0;
if(sta[u].back()==x){
sta[u].pop_back();
ans.pb(mp(u,0));
}
else{
sta[u].pop_front();
ans.pb(mp(empt,0)),ans.pb(mp(u,empt));
}
}
return 1;
}
void solve(){
cin>>n>>m>>k;
init();
for(int i=1;i<=m;i++)cin>>crd[i];
for(int i=1;i<=m;i++){
if(_push(crd[i]))continue;//先不断插入
//位置不够了
int x=crd[i],pos=i+1;
while(pos<=m&&crd[pos]!=x&&sta[id[crd[pos]]].back()==crd[pos])pos++;
if(crd[pos]==x){//如果就是这个x
ans.pb(mp(empt,0));//放到辅助栈
for(int j=i+1;j<pos;j++)_push(crd[j]);//先自由插入
ans.pb(mp(empt,0));//再消除
i=pos;continue;
}
int cnt=0,a=crd[pos],b=sta[id[crd[pos]]].back();
int p=id[crd[pos]];
for(int j=i+1;j<pos;j++)if(crd[j]==b)cnt++;
if(cnt%2==1){//是奇数
ans.pb(mp(empt,0)),sta[empt].pb(x);
//把x插到辅助栈里
for(int j=i+1;j<pos;j++){
if(crd[j]==b)ans.pb(mp(p,0));//是b就直接插到所在栈
else _push(crd[j]);//不是就自由插入
}
q.push(empt),id[x]=empt,id[a]=id[b]=0;
sta[p].clear();//更新
ans.pb(mp(p,0)),empt=p;//把剩下的插到p里,更换辅助栈
}
else{//是偶数
ans.pb(mp(p,0));//把x插到所在栈上
for(int j=i+1;j<pos;j++){
if(crd[j]==b)ans.pb(mp(empt,0));//其他的插到辅助栈
else _push(crd[j]);
}
id[a]=0,id[x]=p;
ans.pb(mp(empt,0)),ans.pb(mp(p,empt));
sta[p].pop_front(),sta[p].pb(x);//更新
}
i=pos;
}
cout<<ans.size()<<'\n';
for(int i=0;i<ans.size();i++){
if(!ans[i].second)
cout<<"1 "<<ans[i].first<<'\n';
else cout<<"2 "<<ans[i].first<<' '<<ans[i].second<<'\n';
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>T;while(T--)solve();
return 0;
}
P8867 [NOIP2022] 建造军营
tarjan缩点+树形dp。
dp的初始化形如这样：
其中 \(E_u\) 为该边双连通分量的边数，\(V_u\) 为点数，\(dp_{u,0/1}\) 为对于每个连通分量，选或不选城市建造军营。
dp式形如这样：
最后统计答案的时候，若 \(u\) 为根，则 \(ans=ans+dp_{u,1}\)；若 \(u\) 不为根，则 \(ans=ans+dp_{u,1}\times 2^{s_{root}-s_u-1}\)，其中 \(s_u\) 为以 \(u\) 为根的子树中边（缩点前的边）的数量。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mxn 500010
#define mxm 2000010
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define pll pair<ll,ll>
ll n,m,cnt,ts;
ll dfn[mxn],low[mxn],sta[mxn],len,dcc[mxn];
ll vsum[mxn],esum[mxn];
ll dp[mxn][2],ans,mi2[mxm],s[mxn];
bool ins[mxn],vis[mxm];
vector<pll> t[mxn];
vector<int> g[mxn];
map<pll,bool> evis;
void init(){
mi2[0]=1;
for(int i=1;i<=m*2;i++)
mi2[i]=(mi2[i-1]<<1)%mod;
}
void tarjan(int u,int f){
dfn[u]=low[u]=++ts;
for(int i=0;i<t[u].size();i++){
int v=t[u][i].first,num=t[u][i].second;
if(!dfn[v]){
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u])
vis[num]=1,vis[u>v?num-1:num+1]=1;
}
else if(dfn[v]<dfn[u]&&v!=f)
low[u]=min(low[u],dfn[v]);
}
}
void dfs1(int u,int id){
dcc[u]=id,vsum[id]++;
for(int i=0;i<t[u].size();i++){
int v=t[u][i].first,num=t[u][i].second;
if(vis[num]&&dcc[v])
g[id].pb(dcc[v]),g[dcc[v]].pb(id);
else if(!vis[num]&&!dcc[v])dfs1(v,id);
}
}
void dfs2(int u,int f){
s[u]=esum[u];
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(v==f)continue;
dfs2(v,u);
s[u]+=s[v]+1;
}
}
void dfs3(int u,int f){
dp[u][0]=mi2[esum[u]];
dp[u][1]=(mi2[vsum[u]+esum[u]]-mi2[esum[u]]+mod)%mod;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(v==f)continue;
dfs3(v,u);
ll tot=dp[u][1];
dp[u][1]=dp[u][0]*dp[v][1]%mod;
dp[u][1]=(dp[u][1]+tot*((2*dp[v][0]%mod+dp[v][1])%mod)%mod)%mod;
dp[u][0]=(dp[u][0]*(dp[v][0]*2%mod)%mod)%mod;
}
if(u==1)ans=(ans+dp[u][1])%mod;
else ans=(ans+dp[u][1]*mi2[s[1]-s[u]-1]%mod)%mod;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
init();
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;
if(u==v)continue;
if(u>v)swap(u,v);
t[u].pb(mp(v,++cnt)),t[v].pb(mp(u,++cnt));
}
for(int i=1;i<=n;i++)
if(!dfn[i])tarjan(i,0);
cnt=0;
for(int i=1;i<=n;i++)
if(!dcc[i])dfs1(i,++cnt);
for(int i=1;i<=n;i++)
for(int j=0;j<t[i].size();j++){
int v=t[i][j].first;
if(dcc[i]==dcc[v])esum[dcc[i]]++;
}
for(int i=1;i<=cnt;i++)esum[i]/=2;
dfs2(1,0),dfs3(1,0);
cout<<ans<<'\n';
return 0;
}
P8868 [NOIP2022] 比赛
极好的线段树高难度题。
考虑把询问挂线段树上，每次区间合并的时候，对于 \(a\) 和 \(b\) 的最大值在左边还是右边分类讨论，然后大力合并。
合并时对于答案也要开两个线段树查，所以代码巨大难写，巨大难调。
#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define mxn 250010
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define X first
#define Y second
#define il inline
int T,n,q;
pii askk[mxn];
ll ans[mxn],sum1[mxn<<2],a[mxn],b[mxn],maxa[mxn],maxb[mxn];
vector<int> ask[mxn<<2],lft[mxn],rgt[mxn],total;
struct Seg{
ll lazy[mxn<<2],sum2[mxn<<2],bsum[mxn<<2];
il void push_up(int rot){
sum2[rot]=sum2[rot<<1]+sum2[rot<<1|1];
bsum[rot]=bsum[rot<<1]+bsum[rot<<1|1];
}
il void push_down(int rot){
if(!lazy[rot])return;
sum2[rot<<1]+=lazy[rot]*bsum[rot<<1];
sum2[rot<<1|1]+=lazy[rot]*bsum[rot<<1|1];
lazy[rot<<1]+=lazy[rot],lazy[rot<<1|1]+=lazy[rot];
lazy[rot]=0;
}
il void build(int rot,int l,int r,int id){
sum2[rot]=lazy[rot]=bsum[rot]=0;
if(l==r){
if(!id)bsum[rot]=1;
else bsum[rot]=maxb[l];
return;
}
int mid=(l+r)>>1;
build(rot<<1,l,mid,id),build(rot<<1|1,mid+1,r,id);
push_up(rot);
}
il void add(int rot,int l,int r,int x,int y,ll k){
if(r<x||l>y)return;
if(l>=x&&r<=y){
sum2[rot]+=k*bsum[rot],lazy[rot]+=k;
return;
}
push_down(rot);
int mid=(l+r)>>1;
add(rot<<1,l,mid,x,y,k),add(rot<<1|1,mid+1,r,x,y,k);
push_up(rot);
}
il ll query(int rot,int l,int r,int x,int y){
if(l>=x&&r<=y)return sum2[rot];
push_down(rot);
int mid=(l+r)>>1;
ll ret=0;
if(x<=mid)ret+=query(rot<<1,l,mid,x,y);
if(y>mid)ret+=query(rot<<1|1,mid+1,r,x,y);
return ret;
}
}s1,s2;
namespace solver{
il void add(int rot,int l,int r,int x,int y,int id){
if(l>=x&&r<=y){
ask[rot].pb(id);
return;
}
int mid=(l+r)>>1;
if(x>mid)add(rot<<1|1,mid+1,r,x,y,id);
else if(y<=mid)add(rot<<1,l,mid,x,y,id);
else{
ask[rot].pb(id);
add(rot<<1,l,mid,x,y,id);
add(rot<<1|1,mid+1,r,x,y,id);
}
}
il void clear(int l,int r){
total.clear();
for(int i=l;i<=r;i++)
lft[i].clear(),rgt[i].clear();
}
il void init_max(int l,int r){
int mid=(l+r)>>1;
maxa[mid]=a[mid],maxb[mid]=b[mid];
maxa[mid+1]=a[mid+1],maxb[mid+1]=b[mid+1];
for(int i=mid-1;i>=l;i--)
maxa[i]=max(maxa[i+1],a[i]),maxb[i]=max(maxb[i+1],b[i]);
for(int i=mid+2;i<=r;i++)
maxa[i]=max(maxa[i-1],a[i]),maxb[i]=max(maxb[i-1],b[i]);
}
il void solve(int rot,int l,int r){
if(l==r){
sum1[rot]=a[l]*b[l];
for(int id:ask[rot])ans[id]+=sum1[rot];
return;
}
int mid=(l+r)>>1;
solve(rot<<1,l,mid);
solve(rot<<1|1,mid+1,r);
sum1[rot]=sum1[rot<<1]+sum1[rot<<1|1];
clear(l,r);
for(int id:ask[rot])
if(askk[id].X<=l&&askk[id].Y>=r)total.pb(id);
else lft[max(l,askk[id].X)].pb(id),rgt[min(r,askk[id].Y)].pb(id);
init_max(l,r);
s1.build(1,l,mid,0),s2.build(1,l,mid,1);
for(int i=mid+1,j=mid+1,k=mid+1;i<=r;i++){
while(maxa[j-1]<maxa[i]&&j>l)j--;
while(maxb[k-1]<maxb[i]&&k>j)k--;
if(k<=mid)s1.add(1,l,mid,k,mid,maxa[i]*maxb[i]);
if(j<k)s2.add(1,l,mid,j,k-1,maxa[i]);
for(int id:rgt[i]){
int left=max(l,askk[id].X);
ans[id]+=s1.query(1,l,mid,left,mid)+s2.query(1,l,mid,left,mid);
}
}
sum1[rot]+=s1.query(1,l,mid,l,mid)+s2.query(1,l,mid,l,mid);
s1.build(1,mid+1,r,0),s2.build(1,mid+1,r,1);
for(int i=mid,j=mid,k=mid;i>=l;i--){
while(maxa[j+1]<maxa[i]&&j<r)j++;
while(maxb[k+1]<maxb[i]&&k<j)k++;
if(k>mid)s1.add(1,mid+1,r,mid+1,k,maxa[i]*maxb[i]);
if(j>k)s2.add(1,mid+1,r,k+1,j,maxa[i]);
for(int id:lft[i]){
int right=min(r,askk[id].Y);
ans[id]+=s1.query(1,mid+1,r,mid+1,right)+s2.query(1,mid+1,r,mid+1,right);
}
}
sum1[rot]+=s1.query(1,mid+1,r,mid+1,r)+s2.query(1,mid+1,r,mid+1,r);
for(int id:total)ans[id]+=sum1[rot];
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>T>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
cin>>q;
for(int i=1;i<=q;i++){
cin>>askk[i].X>>askk[i].Y;
solver::add(1,1,n,askk[i].X,askk[i].Y,i);
}
solver::solve(1,1,n);
for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
return 0;
}