## 【BZOJ 4197】[NOI2015] 寿司晚宴

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 509;
const int M = 6561;

int pri[] = {2, 3, 5, 7, 11, 13, 17, 19};
int n, gpri[N], spri[N], sta1[M], sta2[M], tt[M][N][3];
LL MOD, *f, *g, *h, arr1[M], arr2[M], arr3[M], ori[M];
vector<int> sta[N];

inline void relax(LL &a, LL b) {
a = (a + b) % MOD;
}

inline int num(int x, int t) {
for (; t; x /= 3, t--);
return x % 3;
}

inline int SET(int w, int t, int v) {
static int buf[] = {1, 3, 9, 27, 81, 243, 729, 2187};
int ret = 0;
for (int i = 0; i < 8; i++, w /= 3, t >>= 1) {
if (t & 1) {
ret += buf[i] * v;
} else {
ret += buf[i] * (w % 3);
}
}
return ret;
}

int main() {
freopen("dinner.in", "r", stdin);
freopen("dinner.out", "w", stdout);
cin>>n>>MOD;
for (int i = 0; i < M; i++) {
for (int j = 0; j < 8; j++) {
int t = num(i, j);
if (t == 1) {
sta1[i] |= 1 << j;
} else if (t == 2) {
sta2[i] |= 1 << j;
}
}
}
for (int i = 0; i < M; i++) {
for (int j = 0; j < (1 << 8); j++) {
for (int k = 1; k <= 2; k++) {
tt[i][j][k] = SET(i, j, k);
}
}
}
for (int i = 2; i <= n; i++) {
gpri[i] = i;
for (int j = 0; j < 8; j++) {
if (gpri[i] % pri[j] == 0) {
spri[i] |= (1 << j);
while (gpri[i] % pri[j] == 0) {
gpri[i] /= pri[j];
}
}
}
}
f = arr1, g = arr2, h = arr3;
g[0] = f[0] = 1;
for (int i = 2; i <= n; i++) {
if (gpri[i] == 1) {
for (int j = M - 1; ~j; j--) {
if (g[j]) {
int sta = 0;
for (int k = 0; k < 8; k++) {
if (spri[i] >> k & 1) {
sta |= num(j, k);
}
}
if (sta == 0) {
relax(f[tt[j][spri[i]][1]], g[j]);
relax(f[tt[j][spri[i]][2]], g[j]);
} else if (sta < 3) {
relax(f[tt[j][spri[i]][sta]], g[j]);
}
}
}
memcpy(g, f, sizeof(arr1));
swap(f, g);
} else {
sta[gpri[i]].push_back(spri[i]);
}
}
for (int i = 2; i <= n; i++) {
if (!sta[i].empty()) {
memcpy(h, g, sizeof(arr1));
memcpy(ori, g, sizeof(arr1));
for (int j = 0; j < (int)sta[i].size(); j++) {
int vv = sta[i][j];
for (int k = M - 1; ~k; k--) {
if (g[k]) {
int s1 = vv & sta1[k];
if (!s1) {
relax(f[tt[k][vv][2]], g[k]);
}
}
}
memcpy(g, f, sizeof(arr1));
swap(f, g);
}
memcpy(f, h, sizeof(arr1));
for (int j = 0; j < (int)sta[i].size(); j++) {
int vv = sta[i][j];
for (int k = M - 1; ~k; k--) {
if (h[k]) {
int s2 = vv & sta2[k];
if (!s2) {
relax(f[tt[k][vv][1]], h[k]);
}
}
}
memcpy(h, f, sizeof(arr1));
swap(f, h);
}
for (int k = 0; k < M; k++) {
f[k] = g[k] = (f[k] + g[k] - ori[k]) % MOD + MOD;
}
}
}
LL ans = 0;
for (int i = 0; i < M; i++) {
relax(ans, f[i]);
}
printf("%lld\n", ans);
return 0;
}


## 【Codeforces 797F】Mice and Holes

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5009;
const LL INF = 1e15;

int n,m,sum,x[N];
LL f[N],tmp,cost[N];
pair<int,int> mdy[N];

inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

int main() {
for (int i=1;i<=n;i++) x[i] = read(), f[i] = INF;
for (int i=1;i<=m;i++) mdy[i].first = read(), sum += (mdy[i].second = read());
if (sum < n) puts("-1"), exit(0);
sort(x+1, x+1+n); sort(mdy+1, mdy+1+m);
for (int j=1,tot,pos;tot=mdy[j].second,pos=mdy[j].first,j<=m;j++) {
for (int i=1;i<=n;i++) cost[i] = abs(x[i] - pos) + cost[i-1];
for (int len=1;len=min(len,tot),tot>0;tot-=len,len<<=1) {
for (int l=n-len+1,r=n;l>0;--l,--r) {
f[r] = min(f[r], cost[r] - cost[l-1] + f[l-1]);
}
}
}
printf("%lld\n",f[n]);
return 0;
}


## 【BZOJ 4182】Shopping

### 解题报告

—————————— UPD 2017.3.19 ——————————

## 【BZOJ 4145】[AMPPZ2014] The Prices

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100+9;
const int M = 65536;

int n,m,cost[N],f[M];
pair<int,int> que[M];

inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

void DFS(int w, int sta, int c) {
if (w == m + 1) {
f[sta] = min(f[sta], c);
} else {
DFS(w+1, sta, c);
DFS(w+1, sta|(1<<w-1), c+cost[w]);
}
}

void update(int t, int sta, int w) {
if (t == m + 1) {
f[sta|w] = min(f[sta|w], f[sta] + f[w]);
} else {
update(t+1, sta, w);
if ((sta&(1<<(t-1))) == 0)
update(t+1, sta, w|(1<<(t-1)));
}
}

int main() {
memset(f,60,sizeof(f));
for (int i=1,d;i<=n;i++) {
for (int j=1;j<=m;j++)
DFS(1, 0, d);
}
for (int i=1,lim=1<<m;i<lim;i++)
que[i] = make_pair(__builtin_popcount(i), i);
sort(que+1, que+(1<<m));
for (int i=1,lim=1<<m;i<lim;i++)
update(1, que[i].second, 0);
printf("%d\n",f[(1<<m)-1]);
return 0;
}


—————————— UPD 2017.2.7 ——————————

for (int i=s;i;i=(i-1)&s) {}

## 【BZOJ 2794】[POI2012] Cloakroom

#### 题解

1）添加物品的顺序没有限制，但实际上是浪费了一些性质
2）DP的是一个bool数组，只记录是否可以凑出，这样实际上也是浪费了信息

★,°:.☆(￣▽￣)/\$:.°★ 。

#### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1000+9;
const int M = 1000000+9;
const int INF = 100000;

struct Event{
int a,b,c,d;
inline Event() {}
inline Event(int _a, int _b, int _c):a(_a),b(_b),c(_c) {}
inline bool operator < (const Event &B) const {return a < B.a;}
}t[N],q[M];

int f[M],arr[M+N<<1],vout[M],tot,n,m,mx;

inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

int main() {
for (int i=1,a,b,c;i<=n;i++) {
arr[++tot] = c; arr[++tot] = b;
t[i] = Event(b, c, a);
}
for (int i=1,a,b,c;i<=m;i++) {
a = read(); b = read(); c = read() + a;
arr[++tot] = a; arr[++tot] = c;
q[i] = Event(a, c, b);
q[i].d = i;
}
sort(arr+1, arr+1+tot);
tot = unique(arr+1, arr+1+tot) - arr - 1;
for (int i=1;i<=n;i++) {
t[i].a = lower_bound(arr+1, arr+1+tot, t[i].a) - arr;
t[i].b = lower_bound(arr+1, arr+1+tot, t[i].b) - arr;
mx = max(mx, t[i].a);
}
for (int i=1;i<=m;i++) {
q[i].a = lower_bound(arr+1, arr+1+tot, q[i].a) - arr;
q[i].b = lower_bound(arr+1, arr+1+tot, q[i].b) - arr;
q[i].a = min(q[i].a, mx);
}
sort(t+1, t+1+n);
sort(q+1, q+1+m);
f[0] = 1e9;
for (int j=1,p1=1;j<=m;j++) {
for (;t[p1].a<=q[j].a&&p1<=n;p1++) {
for (int i=INF-t[p1].c,to=INF;i>=0;i--,to--) {
f[to] = max(f[to], min(f[i], t[p1].b));
}
}
vout[q[j].d] = f[q[j].c] > q[j].b;
}
for (int i=1;i<=m;i++) {
if (vout[i]) puts("TAK");
else puts("NIE");
}
return 0;
}


## 【BZOJ 1042】[HAOI2008] 硬币购物

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;

const int SGZ = 5;
const int MAXN = 100000+9;
const int LIM = 100000;

int c[SGZ],s,d[SGZ];
LL f[MAXN],vout;

char c=getchar(); int ret = 0;
while (c<'0'||c>'9') c=getchar();
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret;
}

void solve(int p, int sz, int w){
if (p == 5) {
if (sz & 1) vout -= f[s-w];
else if (sz) vout += f[s-w];
} else {
solve(p+1,sz,w);
if (w+d[p] <= s) solve(p+1,sz+1,w+d[p]);
}
}

int main(){
for (int i=1;i<=4;i++) c[i] = read(); int T = read(); f[0] = 1;
for (int j=1;j<=4;j++) for (int i=c[j];i<=LIM;i++) f[i] += f[i-c[j]];
while (T--) {
for (int i=1;i<=4;i++) d[i] = read(); s = read();
for (int i=1;i<=4;i++) d[i] = (d[i]+1)*c[i];
vout = f[s]; solve(1,0,0);
printf("%lld\n",vout);
}
return 0;
}


## 【NOI六连测】[D6T1] 互质

1）只有33以内的质因数：这样的话，直接暴力转移即可
2）有33以上的质因数：将拥有相同的、大于33的质因数的数存成一组，像分组背包一样一起转移

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 5000;
const int LIM = 4500;
const int N = 12;

int sed[]={0,2,3,5,7,11,13,17,19,23,29,31,33};
int n,que[MAXN][MAXN],cnt[MAXN];
int t1[MAXN],t2[MAXN],*f,*g;

char c=getchar(); int buf=0,f=1;
while (c<'0'||c>'9'){if(c=='-')f-1;c=getchar();}
while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
return buf*f;
}

int main(){
freopen("prime.in","r",stdin);
freopen("prime.out","w",stdout);
f=t1; g=t2;

for (int i=1,a;i<=n;i++){
int tmp = a, buf = 0;
for (int i=1;i<=N;i++) if (!(tmp%sed[i])) {
while (!(tmp%sed[i])) tmp /= sed[i];
buf |= 1<<(i-1);
}
if (tmp != 1) que[tmp][++cnt[tmp]] = buf;
else for (int i=1;i<=LIM;i++) if (!(i&buf))
f[i|buf] = max(f[i|buf], f[i]+1);
}

for (int i=1;i<=1000;i++){
for (int k=1;k<=LIM;k++) g[k] = f[k];
for (int j=1;j<=cnt[i];j++)	for (int k=1;k<=LIM;k++)
if (!(k&que[i][j])) g[k|que[i][j]] = max(g[k|que[i][j]], f[k]+1);
swap(g,f);
}

int vout = 1;
for (int i=1;i<=LIM;i++)
vout = max(vout, f[i]);
printf("%d\n",vout);

return 0;
}


—————————— UPD 2017.2.1 ——————————