19 2天前两题
格雷码
首先格雷码是可以正逆递推和异或得到的。
模拟不难，异或第\(i\)位即\(k \oplus \large \lfloor\frac{k}{2}\rfloor\)的第 \(i\) 位。
想起来Nim博弈里的那个异或了。
#include<bits/stdc++.h>
using namespace std;
int n,now;
bool jump;
unsigned long long k;
int main(){
freopen("code.in","r",stdin);
freopen("code.out","w",stdout);
scanf("%d %llu",&n,&k);
for(int i=n;i>=1;--i){
now=(k>>(i-1))&1;
printf("%d",jump?!now:now);
jump=now;
}
return 0;
}
括号树
就是把链的问题上树了，每次继承父亲，然后注意回溯。
要想清楚的是，因为求的是合法子串数，所以括号匹配的起点不一定是根节点，如))(())()，如果从根节点开始会导致没有合法的，所以我们栈中要存的应该是上一个左括号所在的位置。
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int read(){
char ch;int x=0,f=1;
while(!isdigit(ch=getchar())){
if(ch=='-') f=-1;
}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
char str[N]={};
int n,head[N],tot,st[N],top,path[N],fa[N];
long long s[N],ans;
struct E{
int to,nxt;
}e[N];
inline void Add(int u,int v){
++tot,e[tot].to=v;e[tot].nxt=head[u],head[u]=tot;
}
inline void dfs(int now){
int res=0;
if(str[now]==')'){
if(top){
res=st[top];
path[now]=path[fa[res]]+1;//计算答案
--top;
}
}
else st[++top]=now;
s[now]=s[fa[now]]+path[now];
for(int i=head[now];i;i=e[i].nxt) dfs(e[i].to);
if(res) st[++top]=res;
else if(top) --top;
}
int main(){
freopen("brackets.in","r",stdin);
freopen("brackets.out","w",stdout);
n=read();
scanf("%s",str+1);
for(int i=2;i<=n;++i){
fa[i]=read();
Add(fa[i],i);
}
dfs(1);
// for(int i=1;i<=n;++i) printf("%lld ",s[i]);
// printf("\n");
for(int i=1;i<=n;++i) ans^=s[i]*i;
printf("%lld",ans);
return 0;
}
Emiya家今天的饭
第一次接触这样的dp剪状态。
首先考虑所有的都小于等于 \(\lfloor \frac{k}{2} \rfloor\) 不是很好处理，所以容斥成：所有满足前两个条件的方案数总和-只有一个大于\(\lfloor \frac{k}{2} \rfloor\)的不合法情况（因为只有一个可能大于啊……）
对于合法状态，我们只要满足每一行只选一个就行了，所以直接设 \(f_{i,j}\) 表示考虑到第 \(i\) 行，选了 \(j\) 个数的总方案数。
则有转移： \(\large f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\times s_i\) 其中\(s_i\) 表示这一行的总和。即这一行可以选或不选。不选就继承上一行的，选则在不选基础上加上上一行 \(j-1\) 的情况 \(\times\) 所有的和（因为每一种都可能被选，每一种选了都可以和前面的所有情况构成新的排列组合）。
对于不合法的，首先我们得枚举不合法的那一列，然后我们得枚举行，满足和上面同等的条件，所以还有一个当前选了多少个。但是这个多少个是分散在不合法的这一列和其他列中的，要分类。具体地：
设 \(g_{i,j,k}\) 表示考虑到第 \(i\) 行，在col 行选了 \(j\) 个，其他行选了 \(k\) ，不合法总数为：
\(\sum\limits_{col=1}^m g_{i,j,k}\)，然后每个内部：\(\large g_{i,j,k}=g_{i-1,j,k}+g_{i-1,j-1,k}\times a_{i,col}+g_{i-1,j,k-1}\times \small(s_i-a_{i,col})\)。
统计答案为 \(\large \sum\limits_{j>k} g_{n,j,k}\)
\(Code\)
#include<bits/stdc++.h>
using namespace std;
long long read(){
char ch;long long x=0,f=1;
while(!isdigit(ch=getchar())){
if(ch=='-') f=-1;
}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int n,m;
const int mod=998244353;
int legal[105][105],ile[105][105][2005];
long long a[105][2005],s[105][2005];
long long ans,mi;
int main(){
n=read(),m=read();
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j) a[i][j]=read(),s[i][j]=(s[i][j-1]+a[i][j])%mod;
}legal[0][0]=1;
for(int i=1;i<=n;++i){
for(int j=0;j<=n;++j){
legal[i][j]=legal[i-1][j];
if(j>0) legal[i][j]=(legal[i][j]+legal[i-1][j-1]*s[i][m]%mod)%mod;
}
}for(int i=1;i<=n;++i) ans+=legal[n][i],ans%=mod;
ile[0][0][0]=1;
for(int col=1;col<=m;++col){
for(int i=1;i<=n;++i){
for(int j=0;j<=n;++j){
for(int k=0;j+k<=n;++k){
ile[i][j][k]=ile[i-1][j][k];
if(j>0) ile[i][j][k]=(ile[i][j][k]+ile[i-1][j-1][k]*a[i][col]%mod)%mod;
if(k>0) ile[i][j][k]=(ile[i][j][k]+ile[i-1][j][k-1]*(s[i][m]-a[i][col])%mod)%mod;
}
}
}
for(int j=0;j<=n;++j){
for(int k=0;j+k<=n;++k){
if(j>k) mi+=ile[n][j][k],mi%=mod;
}
}
}
printf("%lld\n",(ans+mod-mi)%mod);
return 0;
}
下面就是Orz时间，考虑我们只关心 \(j\) 和 \(k\) 的大小关系而不关心具体的数值，所以这两维其实是可以压成一维的。所以我们考虑只枚举不合法的那一列。则 \(\large g_{i,j}=g_{i-1,j}+g_{i-1,j-1}\times a_{i,col}+g_{i-1,j+1}\times \small(s_i-a_{i,col})\) 。表示前 \(i\) 行，当前列的数比其他列的数多了 \(j\) 个。末状态为 \(\sum\limits_{i=1}^n g_{n,i}\) 。然后您就宝箧啦。时间复杂度 \(\mathcal O(n^2m)\)。实际实现过程中为了避免负数下标带来的ub，把g的第二维加上一个 \(n\) 。然后注意到如果只选了前 \(i\) 个，那么当前列最多比其他列多 \(i\) 个，也最多比其他列少 \(i\) 个，所以就是 \([n-i,n+i]\) 。所以转移从 \(n\) 开始，最后统计答案第二位加上 \(n\) 。
#include<bits/stdc++.h>
using namespace std;
long long read(){
char ch;long long x=0,f=1;
while(!isdigit(ch=getchar())){
if(ch=='-') f=-1;
}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int n,m;
const int mod=998244353;
int legal[105][105],ile[105][205];
long long a[105][2005],s[105][2005];
long long ans,mi;
int main(){
n=read(),m=read();
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j) a[i][j]=read(),s[i][j]=(s[i][j-1]+a[i][j])%mod;
}legal[0][0]=1;
for(int i=1;i<=n;++i){
for(int j=0;j<=n;++j){
legal[i][j]=legal[i-1][j];
if(j>0) legal[i][j]=(legal[i][j]+legal[i-1][j-1]*s[i][m]%mod)%mod;
}
}for(int i=1;i<=n;++i) ans+=legal[n][i],ans%=mod;
for(int col=1;col<=m;++col){
for(int i=1;i<=n;++i){
for(int j=n-i;j<=n+i;++j) ile[i][j]=0;
}
ile[0][n]=1;
for(int i=1;i<=n;++i){
for(int j=n-i;j<=n+i;++j){
ile[i][j]=ile[i-1][j];
if(j>0) ile[i][j]+=ile[i-1][j-1]*a[i][col]%mod,ile[i][j]%=mod;
ile[i][j]+=ile[i-1][j+1]*(s[i][m]-a[i][col])%mod,ile[i][j]%=mod;
}
}
for(int i=1;i<=n;++i) mi+=ile[n][n+i],mi%=mod;
}
printf("%lld",(ans+mod-mi)%mod);
// for(int i=1;i<=n;++i){
// for(int j=1;j<=n;++j) printf("%lld ",legal[i][j]);
// printf("\n");
// }
// for(int i=1;i<=n;++i){
// for(int j=1;j<=n;++j){
// for(int k=1;j+k<=n;++k){
// printf("%lld ",ile[i][j][k]);
// printf("/ ");
// }
// printf("// ");
// }
// printf("\n");
// }
return 0;
}
划分
题号回文
臭小明和他的屑代码
首先考虑如何让程序运行时间最小化。
考虑我们现在有一个区间 \([l,r]\)，则有 \(\large\sum\limits_{i=l}^r {A_i}^2 \leq \sum\limits_{i=l}^{k_1} {A_i}^2 + \sum\limits_{i=k_1+1}^{k_2} {A_i}^2 … \sum\limits_{i=k_{n-1}}^{k_n} {A_i}^2\)。其实很容易观察出我们要尽量把这个区间分得多一点，每一部分短一点，具体来说是最后一段（即最长的一段最短）。具体证明根据平方和吧，不是很会。
所以我们考虑dp划分，设 \(dp_{i,j}\) 为当前考虑到第 \(i\) 段程序，结尾是 \(j\) 的最小值。这样是 \(\mathcal O(n^3)\) 的（方程式应该都会），但是可以二分(也许吧），而且可以贪心，在最靠后的可行位置划分，不枚举前面一段的起点。直接更新dp就是 \(\mathcal O(n^2)\)。（看syksykCCC大佬的题解吧，我瞎口糊的）
但是不止于此，我们继续考虑。这时候就要仔细观察。
我们思考转移条件，显然转移是要三个点的，上一段的结尾，设为 \(j\) ，上一段的开头，设为 \(g_j\) ，设到第 \(i\) 位的前缀和为 \(s_i\) 则转移条件为 \(s_{j}-s_{g_j-1}\leq s_i-s_{j}\) 。所以我们有 \(2s_{j}-s_{g_j-1}\leq s_i\) 。
考虑两个性质：
1.决策点和值单调递增，即可以转移到 \(i\) 的区间一定是以1开头的一段连续区间，为了满足最优性，我们肯定选择满足转移条件的最大的 \(j\) 。
2.考虑我们前面有两个点是可以转移过来的，设为 \(j_1\) 和 \(j_2\) （\(j_1\ge j_2\)），那么如果 \(\large 2s_{j_1}-s_{g_{j_1}-1}\leq 2s_{j_2}-s_{g_{j_2}-1}\) ，如果 \(j_1\)不能成为决策点，则 \(j_2\) 也不能成为决策点。
所以考虑维护一个可能的转移点序列，满足值和pos都是单调递增的，具体地：每次转移时找到队列中最大的满足上述条件的决策点 \(j\) ，转移后仅保留 \(j\) 而弹出小于 \(j\) 的满足条件的决策点（实际可以一开始就弹出）。转移完成后，计算前缀值再将 \(i\) 放入队列中，把所有上面条件中那个值小于 \(i\) 的全部弹出。
关于结论的具体证明看这里
毒瘤卡常卡空间！
\(Code\)
\(n^3\)
注意枚举顺序和范围还有初值。
#include<bits/stdc++.h>
using namespace std;
char ch;int x,f;
int read(){
x=0,f=1;
while(!isdigit(ch=getchar())){
if(ch=='-') f=-1;
}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
const int N=404;
int n,ty;
int a[N];
long long dp[N][N],sum[N],ans;
const long long inf=1e18;
int main(){
freopen("partition.in","r",stdin);
freopen("partition.out","w",stdout);
n=read(),ty=read();
for(int i=1;i<=n;++i) a[i]=read(),sum[i]=sum[i-1]+a[i];
for(int i=0;i<=n;++i){
for(int j=0;j<=n;++j) dp[i][j]=inf;
}dp[0][0]=0,ans=inf;
for(int k=1;k<=n;++k){
for(int j=0;j<=k;++j){
for(int i=0;i<=j;++i){
if(sum[j]-sum[i]<=sum[k]-sum[j]){
dp[j][k]=min(dp[j][k],dp[i][j]+(sum[k]-sum[j])*(sum[k]-sum[j]));
}
}
if(k==n) ans=min(ans,dp[j][k]);
}
}
printf("%lld",ans);
return 0;
}
\(n^2\)
#include<bits/stdc++.h>
using namespace std;
char ch;int x,f;
int read(){
x=0,f=1;
while(!isdigit(ch=getchar())){
if(ch=='-') f=-1;
}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
const int N=5005;
int n,ty;
int a[N];
long long dp[N],sum[N],last[N],ans;
const long long inf=1e18;
int main(){
freopen("partition.in","r",stdin);
freopen("partition.out","w",stdout);
n=read(),ty=read();
for(int i=1;i<=n;++i) a[i]=read(),sum[i]=sum[i-1]+a[i];
for(int i=0;i<=n;++i) dp[i]=inf;
dp[0]=0;
for(int k=1;k<=n;++k){
for(int j=0;j<=k;++j){
if(last[j]<=sum[k]-sum[j]){
if(dp[j]+(sum[k]-sum[j])*(sum[k]-sum[j])<dp[k]){
dp[k]=dp[j]+(sum[k]-sum[j])*(sum[k]-sum[j]);last[k]=sum[k]-sum[j];
}
}
}
}
printf("%lld",dp[n]);
return 0;
}
\(n \ 88pts\)
#include<bits/stdc++.h>
using namespace std;
char ch;int x,f;
int read(){
x=0,f=1;
while(!isdigit(ch=getchar())){
if(ch=='-') f=-1;
}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
const int N=5e5+5;
int n,ty,h,t;
int a[N],q[N],pos[N];
long long s[N],ans;//pos为可能的决策点序列
int main(){
// freopen("partition.in","r",stdin);
// freopen("partition.out","w",stdout);
n=read(),ty=read();
for(int i=1;i<=n;++i) a[i]=read(),s[i]=s[i-1]+a[i];
h=t=1;
for(int i=1;i<=n;++i){
for(h;h<t&&2*s[q[h+1]]-s[pos[q[h+1]]]<=s[i];++h);
if(h<=t) pos[i]=q[h];
else pos[i]=i-1;
for(t;h<=t&&2*s[q[t]]-s[pos[q[t]]]>2*s[i]-s[pos[i]];--t);
q[++t]=i;//ans+=(s[i]-s[pos[i]])*(s[i]-s[pos[i]]);
}
for(int i=n;i>=1;i=pos[i]) ans+=(s[i]-s[pos[i]])*(s[i]-s[pos[i]]);
printf("%lld",ans);
return 0;
}
\(n \ 100pts\)
#include<bits/stdc++.h>
using namespace std;
int read(){
char ch;int x=0,f=1;
while(!isdigit(ch=getchar())){
if(ch=='-') f=-1;
}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
void write(__int128 x){
if(x<10) return putchar(x+'0'),void();
write(x/10);putchar(x%10+'0');
}
const int N=4e7+5;
int n,ty,h,t;
int a[N],q[N],pos[N],p[N],l[N],r[N],mod=1073741824,b[N];
long long s[N];
__int128 ans;
__int128 d(__int128 x){
return x*x;
}
int main(){
n=read(),ty=read();
if(ty){
int x=read(),y=read(),z=read();
b[1]=read(),b[2]=read();
int m=read();
for(int i=1;i<=m;++i) p[i]=read(),l[i]=read(),r[i]=read();
for(int i=3;i<=n;++i) b[i]=((long long)b[i-1]*x%mod+(long long)b[i-2]*y%mod+z)%mod;
for(int i=1;i<=m;++i){
for(int j=p[i-1]+1;j<=p[i];++j){
a[j]=(b[j]%(r[i]-l[i]+1))+l[i];s[j]=s[j-1]+a[j];
}
}
}else{
for(int i=1;i<=n;++i) a[i]=read(),s[i]=s[i-1]+a[i];
}
h=t=1;
for(int i=1;i<=n;++i){
for(;h<t&&2*s[q[h+1]]-s[pos[q[h+1]]]<=s[i];++h);
if(h<=t) pos[i]=q[h];
else pos[i]=i-1;
for(;h<=t&&2*s[q[t]]-s[pos[q[t]]]>2*s[i]-s[pos[i]];--t);
q[++t]=i;
}
for(int i=n;i>=1;i=pos[i]) ans+=d(s[i]-s[pos[i]]);
write(ans);
return 0;
}
难道考场上写挂了暴力还要写个dp来划分来调吗
Orz KSkun