NOIP模擬78
T1 F
解題思路
由於 a 和 b 有一一對應的關係，因此實際上可能的答案只有 n 種。
對於每一種可能的答案可以直接掃一遍 a 數組看是否在 b 數組中是否一一匹配。
可以用 Hash 表，map 或者是 multiset 來維護。。
code
#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=2e3+10;
int n,top,sta[N*N],a[N],b[N],s[N];
unordered_multiset<int> res;
bool check(int temp)
{
res.clear(); for(int i=1;i<=n;i++) res.insert(b[i]);
for(int i=1;i<=n;i++)
{
int num=temp^a[i];
if(res.find(num)==res.end()) return false;
res.erase(res.find(num));
}
return true;
}
signed main()
{
freopen("f.in","r",stdin); freopen("f.out","w",stdout);
n=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) b[i]=read();
for(int i=1;i<=n;i++)
if(check(a[1]^b[i]))sta[++top]=a[1]^b[i];
sort(sta+1,sta+top+1); top=unique(sta+1,sta+top+1)-sta-1;
printf("%lld\n",top);
for(int i=1;i<=top;i++) printf("%lld\n",sta[i]);
return 0;
}
T2 S
解題思路
然而我只會模擬，正著掃是 10pts ，反著掃就是 50pts ，一結合就 60pts，然而我只有 10pts 。
正解是 DP ，對於同一種顏色內部的順序肯定是不會改變的，於是假設位置在 \(i\) 的顏色最後的位置是 \(j\) 那麼交換次數就是 \(j-i-相同顏色個數\) 。
DP 過程就是構建序列了 設 \(f_{i,j,k,0/1/2}\) 表示前 \(i\) 個有 \(j\) 個 R ， \(k\) 個 G 最後結尾是什麼答案。
那麼發現可以滾掉一位，並且當前 Y 個數也可以算出來，轉移即可。
code
#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=410,INF=0x3f3f3f3f3f3f3f3f;
int n,ans=INF,s[N],f[2][N][N][3],cnt[3][N];
char ch[N];
vector<int> v[3];
signed main()
{
freopen("s.in","r",stdin); freopen("s.out","w",stdout);
n=read(); scanf("%s",ch+1); memset(f,0x3f,sizeof(f));
for(int i=0;i<=2;i++) v[i].push_back(0);
for(int i=1;i<=n;i++)
{
for(int j=0;j<=2;j++) cnt[j][i]=cnt[j][i-1];
if(ch[i]=='G') s[i]=1,cnt[1][i]++;
else if(ch[i]=='Y') s[i]=2,cnt[2][i]++;
else cnt[0][i]++; v[s[i]].push_back(i);
}
for(int i=0;i<=2;i++) if(cnt[i][n]>(n+1)/2) printf("-1"),exit(0);
if(cnt[0][n]) f[1][1][0][0]=0;
if(cnt[1][n]) f[1][0][1][1]=0;
if(cnt[2][n]) f[1][0][0][2]=0;
for(int i=1,mxa,mxb;i<n;i++)
{
for(int j=0;j<=cnt[0][n];j++)
for(int k=0;k<=cnt[1][n];k++)
fill(f[(i&1)^1][j][k]+0,f[(i&1)^1][j][k]+3,INF);
mxa=min(i,cnt[0][n]);
for(int j=0;j<=mxa;j++)
{
mxb=min(i-j,cnt[1][n]);
for(int k=0;k<=mxb;k++)
{
int p=i-j-k; if(p<0) continue;
for(int pos=0;pos<=2;pos++)
{
if(f[i&1][j][k][pos]==INF) continue;
if(pos&&j<cnt[0][n]) f[(i&1)^1][j+1][k][0]=min(f[(i&1)^1][j+1][k][0],f[i&1][j][k][pos]+max(0ll,k-cnt[1][v[0][j+1]])+max(0ll,p-cnt[2][v[0][j+1]]));
if(pos!=1&&k<cnt[1][n]) f[(i&1)^1][j][k+1][1]=min(f[(i&1)^1][j][k+1][1],f[i&1][j][k][pos]+max(0ll,j-cnt[0][v[1][k+1]])+max(0ll,p-cnt[2][v[1][k+1]]));
if(pos!=2&&p<cnt[2][n]) f[(i&1)^1][j][k][2]=min(f[(i&1)^1][j][k][2],f[i&1][j][k][pos]+max(0ll,j-cnt[0][v[2][p+1]])+max(0ll,k-cnt[1][v[2][p+1]]));
}
}
}
}
for(int i=0;i<=2;i++) ans=min(ans,f[n&1][cnt[0][n]][cnt[1][n]][i]);
printf("%lld",ans);
return 0;
}
T3 Y
解題思路
code
#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=1e6+10,mod=1e9+7;
int n,s[N],f[N][2],inv2,inv6;
int power(int x,int y,int p=mod)
{
int temp=1;
while(y)
{
if(y&1) temp=temp*x%p;
x=x*x%p; y>>=1;
}
return temp;
}
int g1(int x){return x%=mod,x*(x+1)%mod*inv2%mod;}
int g2(int x){return x%=mod,x*(x+1)%mod*(2*x+1)%mod*inv6%mod;}
int solve(int base,int lim)
{
memset(f,0,sizeof(f)); f[1][0]=base; f[1][1]=base^1;
for(int i=1;i<=n;i++)
{
int num=s[i]-lim;
f[i+1][0]=(f[i+1][0]+f[i][0]*g1(num)%mod+f[i][1]*(num+1)%mod)%mod;
num+=lim; f[i+1][1]=(f[i+1][1]+f[i][0]*(num*g1(num)%mod-g2(num)+mod)%mod+f[i][1]*g1(num)%mod)%mod;
}
return f[n+1][base^1];
}
signed main()
{
freopen("y.in","r",stdin); freopen("y.out","w",stdout);
n=read(); inv2=power(2,mod-2); inv6=power(6,mod-2);
for(int i=1;i<=n;i++) s[i]=read();
printf("%lld",(solve(1,0)+solve(0,0)-solve(1,1)-solve(0,1)+2*mod)%mod);
return 0;
}
T4 O
解題思路
假作法，思路來自 zxb （數據是真的水，幾乎都是單調遞增的。。）
維護一個由棧底到棧頂單調遞減的棧，每次暴掃單調棧，記錄下當前的火苗會在哪一個時刻變化。
然後每一時刻直接暴力修改，樹狀數組維護加和即可。
code
#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=2e5+10;
int n,m,pos=1,top,sta[N],s[N],ans[N];
vector< pair<int,int> > v[N];
struct Node{int id,t,l,r;}q[N];
struct BIT
{
int tre[N];
inline int lowbit(register int x){return x&(-x);}
inline void insert(register int x,register int val){for(register int i=x;i<=n;i+=lowbit(i))tre[i]+=val;}
inline int query(register int x){register int sum=0;for(register int i=x;i;i-=lowbit(i))sum+=tre[i];return sum;}
inline int query(register int l,register int r){return query(r)-query(l-1);}
}T;
bool comp(Node x,Node y){return x.t<y.t;}
signed main()
{
freopen("o.in","r",stdin); freopen("o.out","w",stdout);
n=read(); m=read();
for(register int i=1;i<=n;i++)
{
s[i]=read(); T.insert(i,s[i]);
while(top&&s[sta[top]]<=s[i]) top--;
for(register int j=1;j<=top;j++) v[i-sta[j]].push_back(make_pair(i,s[sta[j]]));
sta[++top]=i;
}
for(register int i=1,t,l,r;i<=m;i++) t=read(),l=read(),r=read(),q[i]=(Node){i,min(t,n),l,r}; sort(q+1,q+m+1,comp);
for(register int i=1;i<=n&&pos<=m;i++)
{
for(register int j=0;j<v[i].size();j++) T.insert(v[i][j].first,v[i][j].second-s[v[i][j].first]),s[v[i][j].first]=v[i][j].second;
while(pos<=m&&q[pos].t==i) ans[q[pos].id]=T.query(q[pos].l,q[pos].r),pos++;
}
for(register int i=1;i<=m;i++) printf("%lld\n",ans[i]);
return 0;
}
