公司做网站需要提供的材料,怎么给自己的公司做网站,门户网站的建设费用,部分网站建设管理不规范简单的区间 $update$ 终于$AC$了 找到$(sum[r]sum[l](sum表示以中间点为基准的sum)-mx)\%k0$的点 注意这里$sum$表示是以$mid$为基准点,(即$sum[l]$为后缀和,$sum[r]$为前缀和) 回忆$(sum[r]-sum[l])\%k0$这个经典问题做法(入阵曲简化版),开桶,桶里维护$sum[l]\%k$,那么$r$贡献… 简单的区间 $update$ 终于$AC$了 找到$(sum[r]sum[l](sum表示以中间点为基准的sum)-mx)\%k0$的点 注意这里$sum$表示是以$mid$为基准点,(即$sum[l]$为后缀和,$sum[r]$为前缀和) 回忆$(sum[r]-sum[l])\%k0$这个经典问题做法(入阵曲简化版),开桶,桶里维护$sum[l]\%k$,那么$r$贡献就是桶里$sum[r]\%k$个数 于是这个题开桶维护$sum$,问题转化为求$max$即可 记录$max$位置是否$mid$,区别对待 设$f[i][0]$表示$max$在$mid$右面,$f[i][1]$表示$max$在$mid$左面 $f[i][0]$存下右面$sum[r]-mx$,找桶里是否存在左面$sum[l]$$f[i][1]$存下右面$sum[r]$ 找到左面是否存在$mx-sum[l]$完了 #includebits/stdc.h
using namespace std;
#define ll long long
#define A 1010101
ll f[A][2],a[A],pos[A],mx[A],sum[A];
ll cnt,n,k,ans;
void solve(ll l,ll r){if(lr) return ;ll mid(lr)1;cntsum[mid]mx[0]0;for(ll imid1;ir;i){if(a[i]a[mx[cnt]]) mx[cnt]i;sum[i](sum[i-1]a[i])%k;f[(sum[i]-a[mx[cnt]]%kk)%k][0];pos[i]mx[cnt];
// printf(f[%lld]%lld sum%lld cnt%lld\n,(sum[i]-a[mx[cnt]]%kk)%k,f[(sum[i]-a[mx[cnt]]%kk)%k][0],sum[i],cnt);}mx[cnt1]r1;ll suml0,rnowmid1,mxl0,p1;for(ll imid;il;i--){suml(sumla[i])%k;mxlmax(mxl,a[i]);while(pcnta[mx[p]]mxl) p;while(rnowmx[p]) {f[(sum[rnow]-a[pos[rnow]]%kk)%k][0]--;f[sum[rnow]%k][1];rnow;}
// printf(ans%lld f[%lld][1]%lld p%lld rnow%lld mx[%lld]%lldsum[%lld]%lld\n,ans,(kmxl%k-suml)%k,f[(kmxl%k-suml)%k][1],p,rnow,p,mx[p],rnow,sum[rnow]);ansf[(mxl-sumlk)%k][1];if(pcnt) ansf[(k-suml)%k][0];
// printf(ans%lld f[%lld][0]%lld\n,ans,k-suml,f[(k-suml)%k][0]);}for(ll imid1;irnow;i)f[sum[i]][1]--;for(ll irnow;ir;i)f[(sum[i]-a[pos[i]]%kk)%k][0]--;solve(l,mid);solve(mid1,r);
}
int main(){scanf(%lld%lld,n,k);for(ll i1;in;i)scanf(%lld,a[i]);solve(1,n);printf(%lld,ans);
} View Code 简单的玄学 题解 题目中说至少两个相同那么答案就所有方案-全不相同 所有方案${(2^n)}^m2^{n*m}$, 互不相同,首先第一个随便选剩下避开已经选过就行$2^n*2^{n-1}......2^{n-m1}$ 那么题目很傻逼的让你取模并且约分,你需要先约分再取模(取模再约分的话这个题就太水了,所以是先约分再取模) 思考怎么约分 下面全是$2$多少次方,于是我们看上面多少个二就行了 $2^n*(2^{n}-1)......({2^n}-m1)$很恶心,思考转化 性质:$2^n-x$中二个数$$$x$中二的个数 证明:假设$x$可以表示为$j*(2^w)$(j可以是分数),乘法分配率$2^w*(2^{n-w}-j)$后面这个里面没有别的$2$因子了,原式$$$2^w$,又$j$中没有$2$因子故相乘因子数不变,得证 那么原式就变成求$(m-1)!$里$2$因子数 可以简单求 for(ll i1;(1lli)m-1;i){(ercnt(m-1)/(1lli));} 例如$1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$这个序列 分别有$(2^1)*2$,$(2^2)*1$,$(2^3)*1$那么就是$8/88/48/2$ 可以看作$/2$时给所有有$2$因子填上一个二(即$2$,$4$,$6$,$8$中填一个2),此时$4$还剩$1$个没填$8$还剩$2$个没填 $/4$给$4$,$8$里填此时$8$还剩$1$个没填 最后$/8$,全部填满 代码 #includebits/stdc.h
using namespace std;
#define ll long long
const ll mod1e63;
const ll phi1e62;
ll x,y,n,m;
ll meng(ll x,ll k){ll ans1;for(;k;k1,xx*x%mod)if(k1)ansans*x%mod;return ans;
}
ll gcd(ll x,ll y){if(y0) return x;return gcd(y,x%y);
}
int main(){
// freopen(sd.txt,w,stdout);scanf(%lld%lld,n,m);
/* if(log(m)n){printf(1 1\n);return 0;}
*/ ll maxnmeng(2,n%phi);ymeng(maxn,m%phi);x1;ll ercntn; for(ll i0;im;i){
// printf(maxn-i%lld i%lld m%lld x%lld\n,maxn-i,i,m,x);xx*(maxn-i)%mod;if(!x) break;}//2逆元500002for(ll i1;(1lli)m-1;i){(ercnt(m-1)/(1lli));printf(ercnt%lld 1%lld\n,ercnt-n,1lli);}yy*meng(500002,ercnt)%mod;xx*meng(500002,ercnt)%mod;printf(%lld %lld\n,(y-xmod)%mod,y);
} View Code 简单的填数 题解 一个$up$代表填的上界,$down$代表填的下界 先不考虑已经填了的 $up$两位一进,$down$五位一进 考虑已经填的 先考虑上界 若$a[i]up$比上界大肯定不合法 若$a[i]up$取$min(2,up)$ 若$a[i]up$则将$up$调整到$a[i]$次数变为$2$ 下界类似 若$a[i]down$比下界小不合法 若$a[i]down$将$down$调整到$a[i]$ 统计答案时反着扫 序列为什么不是$up$呢 7
0 0 0 2 0 2 0
正解
2
1 1 2 2 2 2 2
用up:
2
1 1 2 2 3 2 2 代码 /*
7
0 0 0 2 0 2 0
hack
2
1 1 2 2 2 2 2
up:
2
1 1 2 2 3 2 2
10f
*/
#includebits/stdc.h
using namespace std;
#define ll long long
#define A 1010101
struct node {ll cnt,x;
}up[A],down[A];
ll n;
ll a[A],tong[A];
int main(){
// freopen(da.in,r,stdin); freopen(ans.bf,w,stdout);scanf(%lld,n);for(ll i1;in;i){scanf(%lld,a[i]);}if(a[1]!1a[1]!0){printf(-1\n);return 0;}up[1].cnt1,up[1].x1;down[1].cnt1,down[1].x1;for(ll i2;in;i){up[i]up[i-1],down[i]down[i-1];if(up[i].cnt2) up[i].cnt1,up[i].x;if(down[i].cnt5) down[i].cnt1,down[i].x;if(a[i]){if(up[i].xa[i]){up[i].xa[i];up[i].cnt2;}else if(up[i].xa[i]){up[i].cntmin(up[i].cnt,2ll);}if(down[i].xa[i])down[i].xa[i],down[i].cnt1;if(up[i].xa[i]||down[i].xa[i]){printf(-1\n);return 0;}}}if(up[n].cnt1){up[n].xup[n-1].x;}if(up[n].xdown[n].x){printf(-1\n);return 0;}printf(%lld\n,up[n].x);tong[up[n].x]1;a[n]up[n].x;for(ll in-1;i1;i--){if(!a[i]){ll tmin(a[i1],up[i].x);if(tong[t]5) t--;a[i]t;}tong[a[i]];}for(ll i1;in;i){printf(%lld ,a[i]);}
} View Code 简单的序列 这是一个简单$dp$,但我觉得很棒在此写下题解 真的非常简单, 有一个长度$n$括号序列(只有$()$ ),给定其中长度为$m$一段,求满足括号匹配方案数 $n,m1e6$ $n-m4000$ 题解 性质:我们发现一个合法匹配序列左扩号时刻比右括号多(显然),最后左扩号数量等于右括号数量 设$f[i][j]$表示长度为$i$序列,左扩号比右括号多$j$个方案数 那么类似的设$g[i][j]$为右括号比左扩号多$j$的方案数 (其实$f$和$g$值完全一样) 转移非常简单 当前括号可能是$($则贡献$f[i][j]f[i-1][j-1]$为$)$则$f[i][j]f[i-1][j1]$ 总贡献$f[i][j]f[i-1][j-1]f[i-1][j1]$ 类似的$g[i][j]g[i-1][j-1]g[i-1][j1]$ 那么思考统计答案 其实也非常简单 枚举第一段长度$i$,第一段左扩号比右括号多$j$,设给定序列左扩号比右括号多$j$ $ans\sum\limits_{i1}^{in-m} \sum\limits_{j0}^{ji} f[i][j]*g[(n-m)-i][jtot]$ 注意判是否合法 代码 #includebits/stdc.h
using namespace std;
#define ll long long
#define A 4040
const ll mod1e97;
char c[2020202];
ll f[A][A];
ll tot,mint,n,m,ans;
int main(){
// freopen(da.in,r,stdin); freopen(ans.bf,w,stdout);scanf(%lld%lld,n,m);scanf(%s,c1);for(ll i1;im;i){if(c[i]()tot;else tot--;if(i1) minttot;else mintmin(mint,tot);}f[0][0]1;for(ll i1;in-m;i){for(ll j0;ji;j){if(j0) f[i][j]f[i-1][j1];else f[i][j](f[i-1][j1]f[i-1][j-1])%mod;}}for(ll i0;in-m;i){for(ll j0;ji;j){if(jmint0jtotn-m)ans(ansf[i][j]*f[(n-m)-i][jtot]%mod)%mod;}}printf(%lld\n,ans);
} View Code 我没数据,也没法提交,和$std$对拍了一下 下面是我的数据生成及对拍 1 #includebits/stdc.h2 using namespace std;3 int main(){4 system(g bf.cpp -o bf);5 system(g sol.cpp -o sol);6 system(g da.cpp -o da);7 int rp0;8 while(rp){9 coutrp ;
10 system(./da);
11 system(./sol);
12 system(./bf);
13 if(system(diff -B -b ans.sol ans.bf)){
14 puts(WA);
15 while(1);
16 }
17 puts(AC);
18 }
19 } 对拍 1 #includebits/stdc.h2 using namespace std;3 int main(){4 freopen(da.in,w,stdout);5 srand(time(NULL));6 7 int mrand()%10000300;8 int crand()%m1;9 while(m-c2000){
10 crand()%m1;
11 }
12 coutm cendl;
13 for(int i1;ic;i){
14 if(rand()%2){
15 printf(();
16 }
17 else printf());
18 }
19 coutendl;
20 } 数据生成 转载于:https://www.cnblogs.com/znsbc-13/p/11474038.html
