Day 1 :
T1 : 期末考试
很水的一道题,但是自己搞了大半天过不了大样例.
最后还A了...
主要思想就是枚举最后一个完成的任务的时间
然后对两部分的代价分类讨论统计一下。
(考试代码,略丑)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline void read(ll &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
#define rg register int
#define rep(i,a,b) for(rg i=(a);i<=(b);++i)
#define per(i,a,b) for(rg i=(a);i>=(b);--i)
const int maxn = 100010;
ll A,B,C;int n,m;
int t[maxn],b[maxn];
namespace work1{
int maxtim = 0;
#define lowbit(x) ((x)&(-x))
struct Bit{
ll c[maxn];
inline void modify(int x,int val){
for(;x <= maxtim;x += lowbit(x))
c[x] += val;
}
inline ll query(int x){
ll ret = 0;
for(;x;x-=lowbit(x)) ret += c[x];
return ret;
}
}sit,sut,sib,sub;
int main(){
ll sum_t = 0,sum_b = 0;
rep(i,1,n){
read(t[i]);
maxtim = max(maxtim,t[i]);
sum_t += t[i];
}
rep(i,1,m){
read(b[i]);
maxtim = max(maxtim,b[i]);
sum_b += b[i];
}
rep(i,1,n) sit.modify(t[i],1),sut.modify(t[i],t[i]);
rep(i,1,m) sib.modify(b[i],1),sub.modify(b[i],b[i]);
ll ans = (1LL<<60);
ll res,lsum_t = 0,rsum_t = sum_t,lsum_b = 0,rsum_b = sum_b;
int lsiz_t = 0,rsiz_t = n,lsiz_b = 0,rsiz_b = m;
rep(i,1,maxtim){
lsiz_t = sit.query(i);rsiz_t = n - lsiz_t;
lsum_t = sut.query(i);rsum_t = sum_t - lsum_t;
lsiz_b = sib.query(i);rsiz_b = m - lsiz_b;
lsum_b = sub.query(i);rsum_b = sum_b - lsum_b;
res = C*(1LL*i*lsiz_t - lsum_t);
ll lc = 1LL*i*lsiz_b - lsum_b;
ll rc = rsum_b - 1LL*i*rsiz_b;
if(B <= A){
res += rc*B;
}else{
if(rc >= lc){
res += lc*A;
rc -= lc;
}else{
res += rc*A;
rc = 0;
}
if(rc != 0){
res += rc*B;
rc = 0;
}
}
ans = min(ans,res);
}
printf("%lld
",ans);
return 0;
}
}
namespace work2{
int main(){
int tim = 0;
rep(i,1,n) read(t[i]);
rep(i,1,m){
read(b[i]);
tim = max(b[i],tim);
}
ll ans = 0;
rep(i,1,n){
if(t[i] >= tim) continue;
ans += (tim - t[i])*C;
}
printf("%lld
",ans);
return 0;
}
}
namespace work3{
int main(){
int minn = 1000000;
rep(i,1,n){
read(t[i]);
minn = min(minn,t[i]);
}
ll can = 0,nd = 0;
rep(i,1,m){
read(b[i]);
if(b[i] < minn) can += minn - b[i];
if(b[i] > minn) nd += b[i] - minn;
}
ll res = 0;
if(B <= A) res += nd*B;
else{
if(can >= nd){
res += nd*A;
nd = 0;
}else{
res += can*A;
nd -= can;
}
if(nd != 0) res += nd*B;
}
printf("%lld
",res);
return 0;
}
}
int main(){
read(A);read(B);read(C);
read(n);read(m);
if(A == 1000000000 && B == 1000000000) work2::main();
else if(C == 10000000000000000LL) work3::main();
else work1::main();
return 0;
}
T2 : 相逢是问候
我们发现每个位置上的值在修改操作中是作为幂出现的.
所以我们不能直接将序列 % p进行维护.
考虑欧拉定理.那么应该 % 上的数应该是phi(p)
或者phi(phi(p))或phi(phi(phi(p)))什么的.
打表观察规律后可以发现一个数最多被phi() log次就会变成1.
所以预处理出来不断phi(p)得到的所有不为1的数.
可以通过维护每个点被修改操作覆盖了多少次来剪枝.
对于最小的被覆盖次数也大于得到的区间就可以直接跳出了.
所以可以用线段树实现这个过程.
复杂度是... (O(nlog^3 n)) !??!?!?!?
不要问我是怎么跑过去的.
UPD : 在bzoj 上听闻管理员把我叉掉了...
然后swm_sxt也说我的代码被叉掉了...
毕姥爷的题解这么说的啊...我是照着题解写的啊...
然后上知乎得知毕姥爷被叉掉了.
... ...
代码已更正.可以过掉目前bzoj上的数据.
(其实就多了一句 ph[++cntp] = 1 )...QAQ
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;static char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
#define rg register int
#define rep(i,a,b) for(rg i=(a);i<=(b);++i)
#define per(i,a,b) for(rg i=(a);i>=(b);--i)
const int maxn = 50010;
inline int phi(int x){
int ret = x;
for(rg i=2;i*i<=x;++i){
if(x % i == 0){
ret /= i;ret *= i-1;
while(x % i == 0) x /= i;
}
}
if(x ^ 1) ret /= x,ret *= x-1;
return ret;
}
int ph[maxn],cntp;
int n,m,p,c;
int a[maxn];
struct Node{
int val,mn;
Node(){val = mn = 0;}
friend Node operator + (const Node &a,const Node &b){
Node c;
c.val = (a.val + b.val) % ph[0];
c.mn = min(a.mn,b.mn);
return c;
}
}T[maxn<<2];
int query(int rt,int l,int r,int L,int R){
if(L <= l && r <= R) return T[rt].val;
int mid = l+r >> 1;
if(R <= mid) return query(rt<<1,l,mid,L,R);
if(L > mid) return query(rt<<1|1,mid+1,r,L,R);
return (query(rt<<1,l,mid,L,R) + query(rt<<1|1,mid+1,r,L,R)) % ph[0];
}
inline int qpow(int x,int p,int mod){
int ret = 1;
for(;p;p>>=1,x=1LL*x*x%mod) if(p&1) ret=1LL*ret*x%mod;
return ret;
}
inline int calc(int x,int t){
int ret = x;
if(ret >= ph[t]) ret = ret % ph[t] + ph[t];
per(i,t,1){
x = ret;
ret = qpow(c,x,ph[i-1]);
if(x && !ret) ret += ph[i-1];
}
return ret % ph[0];
}
void build(int rt,int l,int r){
if(l == r){
T[rt].val = calc(a[l],0);
return ;
}
int mid = l+r >> 1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
T[rt] = T[rt<<1] + T[rt<<1|1];
}
void modify(int rt,int l,int r,int L,int R){
if(T[rt].mn >= cntp) return ;
if(l == r){
T[rt].mn ++ ;
T[rt].val = calc(a[l],T[rt].mn);
return ;
}
int mid = l+r >> 1;
if(L <= mid) modify(rt<<1,l,mid,L,R);
if(R > mid) modify(rt<<1|1,mid+1,r,L,R);
T[rt] = T[rt<<1] + T[rt<<1|1];
}
int main(){
read(n);read(m);read(p);read(c);
ph[cntp = 0] = p;
while(p != 1) ph[++ cntp] = (p = phi(p));
ph[++ cntp] = 1;
rep(i,1,n) read(a[i]);
build(1,1,n);
int opt,l,r;
while(m--){
read(opt);read(l);read(r);
if(opt == 1) printf("%d
",query(1,1,n,l,r));
else modify(1,1,n,l,r);
}
return 0;
}
T3 : 组合数问题
这道题考场上直接Lucas上的.
这道题应该没有办法从数论的角度上来进行优化.
考虑一下这些组合数的具体含义:
注意 : (r < k))不要问我为什么要强调注意这个.
那么这些组合数的含义可以这么理解:
从共n*k个物品中选出%k为r的数目的物品的方案数.
这样就很明显了.设(f[i][j])表示前i个数中选出%k为j的数目的物品的方案数.
矩乘优化dp转移.(O(k^3log n))
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(ll &x){
x=0;static char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
#define rg register int
#define rep(i,a,b) for(rg i=(a);i<=(b);++i)
#define per(i,a,b) for(rg i=(a);i>=(b);--i)
ll p;
struct Matrix{
ll n,m;
ll s[52][52];
void clear(ll n,ll m){
this->n = n;this->m = m;
memset(s,0,sizeof s);
}
friend Matrix operator * (const Matrix &a,const Matrix &b){
Matrix c;c.clear(a.n,b.m);
rep(i,0,c.n-1) rep(j,0,c.m-1) rep(k,0,a.m-1){
c.s[i][j] += 1LL*a.s[i][k]*b.s[k][j] % p;
if(c.s[i][j] >= p) c.s[i][j] -= p;
}return c;
}
};
ll n,k,r;
Matrix A,B;
int main(){
read(n);read(p);read(k);read(r);
A.clear(1,k);A.s[0][0] = 1;
B.clear(k,k);
rep(i,0,k-1){
B.s[i][i] += 1;
B.s[(i-1+k)%k][i] += 1;
}
ll x = 1LL*n*k;
for(;x;x>>=1,B=B*B) if(x&1) A=A*B;
printf("%lld
",A.s[0][r]);
return 0;
}
Day2:
T1 :
暂时还不会,挖坑.
T2 : 分手是祝愿
首先考虑对于一个确定的局面如何确定最优策略.
通过很简单的分析可以发现 : 只要从高位到低位确定即可.
然后通过等价变化,将枚举因数变为枚举倍数,可以做到O(nlogn)求出最优解.
通过上面的过程,我们可以得到一个推论 : 最优方案是唯一的.
应该被操作的位是固定的.
所以在进行dp时我们采用如下定义方式 : 设f[i]表示当前的操作中有i个是正确的.
那么通过对下一步的随意选取,很容易得到方程:(f_i = frac{n-i}{n}*f_{i+1} + frac{i}{n}*f_{i-1})
然后这个东西直接利用系数递推进行转移即可.
设(f_i = B_i*f_{i-1} + C_i)
那么
[f_i = frac{n-i}{n}*(B_{i+1}*f_i+C_{i+1}) + frac{i}{n}*f_{i-1} + 1
]
[(1 - frac{n-i}{n}B_{i+1})f_i = frac{i}{n}f_{i-1} + frac{n-i}{n}C_{i+1} + 1
]
[f_i = frac{frac{i}{n}f_{i-1} + frac{n-i}{n}C_{i+1} + 1}{(1 - frac{n-i}{n}B_{i+1})}
]
可以得到递推关系 :
- (B_i = frac{frac{i}{n}}{(1 - frac{n-i}{n}B_{i+1})})
- (C_i = frac{frac{n-i}{n}C_{i+1} + 1}{(1 - frac{n-i}{n}B_{i+1})})
所以线性计算出系数再线性带入计算即可.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
#define rg register int
#define rep(i,a,b) for(rg i=(a);i<=(b);++i)
#define per(i,a,b) for(rg i=(a);i>=(b);--i)
const int mod = 100003;
const int maxn = 100005;
int a[maxn],tag[maxn],b[maxn],c[maxn],f[maxn];
inline int qpow(int x,int p){
int ret = 1;
for(;p;p>>=1,x=1LL*x*x%mod) if(p&1) ret=1LL*ret*x%mod;
return ret;
}
int main(){
int n,k;read(n);read(k);
rep(i,1,n) read(a[i]);
int s = 0;
per(i,n,1){
int res = a[i];
for(int j=i*2;j<=n;j+=i) res^=tag[j];
tag[i] = res;
s += res;
}
if(s <= k){
rep(i,1,n) s = 1LL*s*i%mod;
printf("%d
",s);
}else{
b[k] = 0;c[k] = f[k] = k;
b[n] = c[n] = 1;
for(int i=n-1,inv;i>k;--i){
b[i] = i;c[i] = ( 1LL*(n-i)*c[i+1] % mod + n)%mod;
inv = qpow( (n-1LL*(n-i)*b[i+1]%mod + mod) % mod,mod-2);
b[i] = 1LL*b[i]*inv % mod;
c[i] = 1LL*c[i]*inv % mod;
}
for(int i=k+1;i<=s;++i){
f[i] = (1LL*b[i]*f[i-1] + c[i])%mod;
}
int ans = f[s];
rep(i,1,n) ans=ans*1ll*i%mod;
printf("%d
",ans);
}
return 0;
}
T3 : 寿司餐厅
说多了都是泪.
临考前考到了一道模型相似的题.
抱着这题肯定能A的心态去写的.
然后最大权闭合子图没调出来.
不说那么多了... ...
首先这道题是网络流没跑.
重点我们需要解决三个限制 :
- 选择区间互相的包含关系
- 不同寿司的第一次取用的额外代价
- 区间与寿司的对应关系.
我们使用最小割模型.
先考虑第一种限制,我们知道一个区间一定会对这个区间的所有子区间进行限制.
但是肯定不允许我们对所有子区间都进行连边限制
我们发现限制是具有传递性的,所以对于区间[l,r]直接向[l+1,r],[l,r-1]限制即可.
对于第二、三种限制,我们对于每个寿司建一个额外节点,连出流量为(mx^2),向汇点的边.
对于所有有用到过这个寿司的区间向对应的寿司节点连边.
这样完成了限制二、三.
然后处理处理细节就好了.具体的细节是什么.. ..
我懒得写了==
(这份代码在速度榜上目前rank1,如果按运行时间从大到小排序的话)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;static char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
#define rg register int
#define rep(i,a,b) for(rg i=(a);i<=(b);++i)
#define per(i,a,b) for(rg i=(a);i>=(b);--i)
const int maxn = 128;
const int maxnode = maxn*maxn;
const int maxedge = maxnode*10;
const int inf = 0x3f3f3f3f;
struct Edge{
int to,next,cap;
}G[maxedge<<1];
int head[maxnode],cnt = 1;
void add(int u,int v,int c){
G[++cnt].to = v;
G[cnt].next = head[u];
head[u] = cnt;
G[cnt].cap = c;
}
inline void insert(int u,int v,int c){
add(u,v,c);add(v,u,0);
}
#define v G[i].to
int q[maxnode],l,r,dis[maxnode];
int S,T;
bool bfs(){
memset(dis,-1,sizeof dis);
dis[S] = 0;l = 0;r = -1;
q[++r] = S;
while(l <= r){
int u = q[l++];
for(int i = head[u];i;i=G[i].next){
if(dis[v] == -1 && G[i].cap){
dis[v] = dis[u] + 1;
q[++r] = v;
}
}
}return dis[T] != -1;
}
int dfs(int u,int f){
if(u == T || f == 0 ) return f;
int ret = 0;
for(int i = head[u];i;i=G[i].next){
if(dis[v] == dis[u] + 1 && G[i].cap){
int x = dfs(v,min(G[i].cap,f));
ret += x;f -= x;
G[i].cap -= x;
G[i^1].cap += x;
if(f == 0) break;
}
}return ret;
}
inline int dinic(){
int ret = 0;
while(bfs()) ret += dfs(S,inf);
return ret;
}
#undef v
int nodecnt = 0;
int a[maxn],id[maxn][maxn],idx[maxn];
int main(){
int n,m;read(n);read(m);
S = ++ nodecnt;T = ++ nodecnt;
int mx = 0;
rep(i,1,n) read(a[i]),mx = max(mx,a[i]);
rep(i,1,mx){
idx[i] = ++ nodecnt;
insert(idx[i],T,m*i*i);
}
int x,ans = 0;
rep(i,1,n) rep(j,i,n) id[i][j] = ++ nodecnt;
rep(i,1,n){
rep(j,i,n){
read(x);
if(i == j) x -= a[i],insert(id[i][j],idx[a[i]],inf);
else{
if(id[i+1][j])insert(id[i][j],id[i+1][j],inf);
if(id[i][j-1])insert(id[i][j],id[i][j-1],inf);
}
if(x > 0) ans += x,insert(S,id[i][j],x);
else insert(id[i][j],T,-x);
}
}
ans -= dinic();
printf("%d
",ans);
return 0;
}