Noip2016 ysy模拟1
1. chess
第一轮,A在(0,0)放棋子。
第二轮,B在每个(x,y)放棋子,满足(x-2,y)或(x-1,y-1)有且仅有1个是A的棋子。
第三轮,A每个(x,y)放棋子,满足(x-2,y)或(x-1,y-1)有且仅有1个是B的棋子。
重复上述过程(2,3),问第t轮后(x0,y0)~(x0+w, y0+h)的棋子情况(A,B,空)
$0\leq t, x0, y0 \leq 10^{12}, 0 \leq w,h \leq 50$
【题解】
有可能有棋子的只可能是点(x,y),其中x+y为偶数,然后按照(x+y)/2的奇偶性来判断是什么棋子。
然后按照上述规律排列每个棋子,发现C(n,m)为偶数的时候是空格。
如何判断C(n,m)是不是偶数?
如果n&m==m,那么C(n,m)是奇数。
# include <stdio.h>
# include <algorithm>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 60;
int w, h;
ll t, x, y;
char s[M][M];
int main() {
freopen("chess.in", "r", stdin);
freopen("chess.out", "w", stdout);
scanf("%lld%lld%lld%d%d", &t, &x, &y, &w, &h);
for (int i=0; i<w; ++i)
for (int j=0; j<h; ++j) {
ll newx = x+i, newy = y+j;
// printf("%lld %lld\n", newx, newy);
ll ss = newx + newy;
if(ss&1) s[i][j] = '.';
else {
ss=ss>>1;
if(ss+1<=t) {
// printf("ss=%lld\n", ss);
if(ss&1) s[i][j] = 'B';
else s[i][j] = 'A';
if((ss&newy) != newy) s[i][j] = '.';
} else s[i][j] = '.';
}
}
for (int i=h-1; i>=0; --i, puts(""))
for (int j=0; j<w; ++j)
printf("%c", s[j][i]);
return 0;
}
// 5 4 1 3 4
2. shop
给出n个点m条边的无向图,标号为0~n-1,其中前p个点有商店,每个商店在l[i]-r[i]时间卖钻石,你需要花t[i]的时间买钻石,求你最多获得钻石数量。
$n, m \leq 50, p \leq 16$。
【题解】
状态压缩,$O(2^{p}pn)$。
# include <stdio.h>
# include <algorithm>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 60;
ll f[1<<18][M];
int n, m, p;
ll dis[M][M];
int l[M], r[M], t[M];
int main() {
freopen("shop.in", "r", stdin);
freopen("shop.out", "w", stdout);
scanf("%d%d%d", &n, &m, &p);
for (int i=0; i<n; ++i) {
for (int j=0; j<n; ++j)
dis[i][j] = 1ll<<40;
dis[i][i] = 0;
}
for (int i=0; i<(1<<p); ++i)
for (int j=0; j<n; ++j) f[i][j] = 1ll<<40;
for (int i=1; i<=m; ++i) {
int u, v;
ll c;
scanf("%d%d%lld", &u, &v, &c);
dis[u][v] = min(dis[u][v], c);
dis[v][u] = min(dis[v][u], c);
}
for (int k=0; k<n; ++k)
for (int i=0; i<n; ++i)
for (int j=0; j<n; ++j)
dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
for (int i=0; i<p; ++i) scanf("%d%d%d", &l[i], &r[i], &t[i]);
f[0][n-1]=0;
int ans = 0;
for (int i=1; i<(1<<p); ++i) {
int mx=0;
for (int j=0; j<p; ++j) {
if(i&(1<<j)) {
++mx;
for (int k=0; k<n; ++k)
if(f[i^(1<<j)][k]+dis[j][k]<=r[j])
f[i][j] = min(f[i][j], max((ll)l[j], f[i^(1<<j)][k]+dis[j][k])+t[j]);
}
}
for (int j=0; j<n; ++j) {
if(f[i][j] < (1ll<<40))
ans = max(ans, mx);
}
}
printf("%d\n", ans);
return 0;
}
3. sequence
最大m子段和。
$m \leq n \leq 10^5, a_i \leq 10^9$。
【题解】
合并每个正段和负段。0合并到正段。然后用堆维护正负段(删除正段,加入负段)。
# include <stdio.h>
# include <algorithm>
# include <set>
# include <iostream>
# include <string.h>
# define abs(x) (x>0?x:-x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 1000010;
int n, m;
ll a[M];
ll b[M];
int bn=0;
int S[M];
int fs[M], fsn=0;
struct node {
ll cur;
int id;
};
bool operator <(node a, node b) {
return a.cur>b.cur;
}
set<node> s;
int fa[M];
int fl[M], fr[M];
inline int getf(int x) {
return fa[x]==x ? x : fa[x] = getf(fa[x]);
}
inline void unions(int fx, int fy) {
fa[fx] = fy;
fl[fy] = min(fl[fy], fl[fx]);
fr[fy] = max(fr[fy], fr[fx]);
}
int main() {
freopen("sequence.in", "r", stdin);
freopen("sequence.out", "w", stdout);
while(~scanf("%d%d", &n, &m)) {
memset(b,0,sizeof(b));
memset(S,0,sizeof(S));
s.clear();
bn=fsn=0;
for (int i=1; i<=n; ++i) scanf("%lld", &a[i]);
int head=1, tail=n;
while(a[head]<0) ++head;
while(a[tail]<0) --tail;
int zf=1;
++bn;
for (int i=head; i<=tail; ++i) {
if(zf*a[i]>0 || (zf==1&&a[i]==0)) {
b[bn]+=a[i];
S[bn]++;
} else {
++bn;
b[bn]=a[i];
S[bn]=1;
zf=-zf;
}
}
int total1=0, total2=0;
ll tot=0;
for (int i=1; i<=bn; ++i) {
if(b[i]>=0) {
total1+=S[i];
total2++;
tot+=b[i];
}
}
if(m >= total2 && m <= total1) {
printf("%lld\n", tot);
} else if(m > total1) {
sort(a+1, a+n+1);
ll ans=0;int k=0;
for (int i=n;i>=1;--i) {
++k;
ans+=a[i];
if(k==m)break;
}
printf("%lld\n", ans);
} else if(m < total2) {
for (int i=1; i<=bn; ++i) {
b[i]=-abs(b[i]);
s.insert((node){b[i],i});
}
int res = total2 - m;
for (int i=1; i<=bn; ++i) fa[i] = i, fl[i] = fr[i] = i;
for (int i=1; i<=res; ++i) {
node x = *s.begin();
s.erase(x);
int fx = x.id, fll = fl[fx], frr = fr[fx];
tot=tot+x.cur;
int left=-1,right=-1;
if(fll > 1) left=getf(fll-1);
if(frr < bn) right=getf(frr+1);
b[fx]=-b[fx];
if(left!=-1) {
s.erase((node){b[left], left});
unions(left, fx);
b[fx]+=b[left];
}
if(right!=-1) {
s.erase((node){b[right], right});
unions(right, fx);
b[fx]+=b[right];
}
if(left!=-1 && right!=-1)
s.insert((node){b[fx],fx});
}
printf("%lld\n", tot);
}
}
return 0;
}