[题解]ZOJ Monthly, August 2012

Decode(ZOJ 3636)

给定k个长度为n的01向量以及异或运算，就得到了一个集合S($$ x \in S $$当且仅当从k个向量中取若干个异或起来可以得到x)。再给定m个询问，每个询问包含一个01向量，要求你在容错位最多为3的前提下找一个离该向量最近并属于S的01向量。如果有多个，输出字典序最小的。

想想如果给你一个01向量，让你判断它在不在S里这是很容易办到的。具体做法就是$$x_i$$表示那k个向量的取和不取的状态，然后得到一个异或方程，高斯消元就可以了。但是注意到这里n只有30，所以那么多向量是没有用的，直接把给的向量消成上三角矩阵，得到其中有用的若干个，就可以在$$O(n)$$的复杂度内判断一个码在不在集合S内了。又由于每个码只允许改3个位，只需暴力枚举改哪三个位再用上面的方法判断就行了。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template  void checkmin(T &t,T x){if (x < t) t = x;}
template  void checkmax(T &t,T x){if (x > t) t = x;}
typedef pair  PII;
typedef pair  PDD;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)

int n, m, q;
vector  base;

void get_base() {
	vector  vec;
	for (int i = n - 1; i >= 0; i--) {
		for (int j = 0; j < base.size(); j++) {
			if (base[j] & (1 << i)) {
				int x = base[j];
				vec.push_back(x);
				for (int k = 0; k < base.size(); k++) {
					if (base[k] & (1 << i)) {
						base[k] ^= x;
					}
				}
				break;
			}
		}
	}
	base = vec;
}

void output(int x) {
	for (int i = n - 1; i >= 0; i--) {
		printf("%d", (bool)((1 << i) & x));
	}
	puts("");
}

bool check(int mask) {
	int now = 0, j = 0;
	for (int i = n - 1; i >= 0 && now != mask; i--) {
		if (((1 << i) & mask) != ((1 << i) & now)) {
			while (j < base.size() && (!((1 << i) & base[j]) || base[j] >= (1 << i + 1))) {
				j++;
			}
			if (j == base.size()) {
				return 0;
			} else {
				now ^= base[j++];
			}
		}
	}
	return 1;
}

void gao(int x) {
	int mask = (1 << n) - 1;
	int ans = 0x7FFFFFFF;
	int best = 10;
	for (int i = 0; i <= n; i++) {
		for (int j = (i == n) ? n : i + 1; j <= n; j++) {
			for (int k = (j == n) ? n : j + 1; k <= n; k++) {
				int now = (i != n) + (j != n) + (k != n);
				int tmp = x ^ (1 << i) ^ (1 << j) ^ (1 << k);
				tmp &= mask;
				if ((now < best || (now == best && tmp < ans)) && check(tmp)) {
					best = now;
					ans = tmp;
				}
			}
		}
	}
	if (ans == 0x7FFFFFFF) {
		puts("NA");
	} else {
		output(ans);
	}
}

int main(){
#ifdef cwj
	freopen("input.txt", "r", stdin);
#endif
	while (scanf("%d %d %d", &n, &m, &q) != EOF) {
		base.clear();
		char buf[50];
		int x;
		for (int i = 0; i < m; i++) {
			scanf("%s", buf);
			x = 0;
			for (int i = 0; i < n; i++) {
				if (buf[i] == '1') {
					x |= (1 << (n - i - 1));
				}
			}
			base.push_back(x);
		}
		get_base();
		for (int i = 0; i < q; i++) {
			scanf("%s", buf);
			x = 0;
			for (int i = 0; i < n; i++) {
				if (buf[i] == '1') {
					x |= (1 << (n - i - 1));
				}
			}
			gao(x);
		}
	}
}

Alice's present(ZOJ 3633)

给定一个序列$$a_i$$，每次询问一个区间内，从右往左看，第一个重复的是谁

设next[i]表示a[next[i]] = a[i]且next[i] > i的最小值，那么询问按左端点排序以后，按其降序扫过去，然后每个询问(l, r)相当于问next[i] ≤ r 的值里最大的i所对应的a[i]是多少。这个显然可以树状数组求最值，就是按next[i]为下标建立树状数组然后blablabla...其实sort后可以$$O(n)$$地用单调队列搞，按类似的思路做也不难实现。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template  void checkmin(T &t,T x){if (x < t) t = x;}
template  void checkmax(T &t,T x){if (x > t) t = x;}
typedef pair  PII;
typedef pair  PDD;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
const int N = 505555;
const int INF = 0x7FFFFFFF;
int n, m;
int a[N];
int next[N];
int pre[N];
map  app;

struct Node {
	int l, r, id, ans;
	bool operator < (const Node &oth) const {
		if (l != oth.l) return l < oth.l;
		if (r != oth.r) return r < oth.r;
		return id < oth.id;
	}
}q[N];

int Tr[N];

bool cmp(Node A, Node B) {
	return A.id < B.id;
}

void Insert(int i, int x) {
	for (;i <= n; i += i & -i) {
		checkmax(Tr[i], x);
	}
}

int get_answer(int i) {
	int ret = -INF;
	for (; i; i -= i & -i) {
		checkmax(ret, Tr[i]);
	}
	if (ret < 0) return -1;
	return a[ret];
}

int main(){
#ifdef cwj
	freopen("in", "r", stdin);
#endif
	while (scanf("%d", &n) != EOF) {
		app.clear();
		for (int i = 1; i <= n; i++) {
			next[i] = -1;
		}
		for (int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
			if (!app.count(a[i])) {
				pre[i] = -1;
			} else {
				pre[i] = app[a[i]];
				next[app[a[i]]] = i;
			}
			app[a[i]] = i;
		}
		scanf("%d", &m);
		for (int i = 0; i < m; i++) {
			scanf("%d%d", &q[i].l, &q[i].r);
			q[i].id = i;
		}
		sort(q, q+m);
		for (int i = 1; i <= n; i++) Tr[i] = -INF;
		int j = n;
		for (int i = m - 1; i >= 0; i--) {
			while (j >= q[i].l) {
				if (next[j] != -1) {
					Insert(next[j], j);
				}
				j--;
			}
			int ret = get_answer(q[i].r);
			q[i].ans = ret;
		}
		sort(q, q + m, cmp);
		for (int i = 0; i < m; i++) {
			if (q[i].ans == -1) {
				puts("OK");
			} else {
				printf("%d\n", q[i].ans);
			}
		}
		puts("");
	}
}

Bounty Hunter(ZOJ 3634)

有一只Bounty Hunter，他按顺序从城市1跑到城市n，在每个城市进行两个操作：买攻击力和做任务。在城市i，每点攻击力要花费$$a_i$$块钱。买完攻击力以后做任务时可以获得$$atp * b_i$$(atp为当时的攻击力)的钱，问最后Bounty Hunter最多能获得多少钱。

设mow[i]表示如果你在进入第i个城市之前，有1块钱，那么在之后最多能变成多少块钱，apw[i]表示如果你在进入第i个城市之前，有1点攻击力，那么在之后最多会演化成多少块钱，然后转移就很显然了，不懂就看代码吧...就像dp一样的思路，唯一需要说明的一点大概是：因为这个转换关系都是常数倍的关系，所以这些获利都可以分开考虑，最后叠加。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template  void checkmin(T &t,T x){if (x < t) t = x;}
template  void checkmax(T &t,T x){if (x > t) t = x;}
typedef pair  PII;
typedef pair  PDD;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
const int N = 105555;
int n, X, Y;
double a[N], b[N];
double mow[N], apw[N];

int main(){
#ifdef cwj
	freopen("in", "r", stdin);
#endif
	while (scanf("%d%d%d", &n, &X, &Y) != EOF) {
		for (int i = 1; i <= n; i++) {
			scanf("%lf %lf", &a[i], &b[i]);
		}
		if (n == 0) {
			printf("%.2lf\n", X);
		} else {
			apw[n] = b[n];
			mow[n] = max(1.0 / a[n] * b[n], 1.0);
			for (int i = n - 1; i >= 0; i--) {
				apw[i] = apw[i + 1] + mow[i + 1] * b[i];
				mow[i] = max(1.0 / a[i] * b[i] * mow[i + 1] + apw[i + 1] * 1.0 / a[i], mow[i + 1]);
			}
			printf("%.2lf\n", X * mow[1] + Y * apw[1]);
		}
	}
}

Information Sharing(ZOJ 3641)

给定每个人身上所带的消息以及若干个集合的合并操作，每次动态问某个人所属的集合中，拥有的信息有哪一些。

因为保证信息数不超过1000，那么1000 * n bitset Disjoint Set暴力合并随便搞。
其实把信息数的条件去掉也可以做的，但是要保证答案size不超过多大或者直接换成输出拥有的信息的数目。这样子的做法大致是两个集合合并的时候，Disjoint Set依然是路径压缩式合并，但是set的合并要从set.size()比较小的那个逐个暴力插入到大的set里面。因为每个人最多只带10个信息，这样可以保证最后复杂度不超过$$O(10n log^2 10n)$$。

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

const int N=100005;

int n,m;
int F[N];
map  Ref;
vector  L[N];
char buf[1005];

string Get(){
    scanf("%s",buf);
    string ret(buf);
    return ret;
}

void gao_arrive(){
     Ref[Get()]=++m;
     F[m]=m;
     L[m].clear();
     int k,x;
     scanf("%d",&k);
     for (int i=0;i=L[y].size() || L[x][i]
Just Another Information Sharing Problem(ZOJ 3642)
有若干个人，第i个人有$$a_i$$条信息，他至少共享$$b_i$$条，至多共享$$c_i$$条，问里面的某个人他最多能获得多少消息。
很显然的网络流。就是S流到人，人再流到信息，信息再流到汇这种模型。唯一要注意的是，自己这个人本来就知道的信息不需要让别人来共享了。
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N=205;
const int INF=0x7FFFFFFF;
int n,m,S,T;
set  Hash;
map  Ref;
int mat[205][15];
int Out[205];

struct Sap{
    int e;
    struct edge{int x,y,c;edge *next,*op;}g[1000000],*ls[105555],*cur[105555],*fa[105555];
    int d[105555];
    int Num[105555];
    int Flow;

    void addedge(int x,int y,int c){
        g[++e].x=x; g[e].y=y; g[e].c=c; g[e].next=ls[x]; ls[x]=&g[e]; g[e].op=&g[e+1];
        g[++e].x=y; g[e].y=x; g[e].c=0; g[e].next=ls[y]; ls[y]=&g[e]; g[e].op=&g[e-1];
//        printf("Edge: %d %d %d\n",x,y,c);
    }

    void clear(){
        e=0;
        memset(ls,0,sizeof(ls));
        memset(Num,0,sizeof(Num));
    }

    void change(){
        int nf=INF;
        for (int i=T;i!=S;i=fa[i]->x)
            if (fa[i]->cc;
        Flow+=nf;
        for (int i=T;i!=S;i=fa[i]->x){
            fa[i]->c-=nf;
            fa[i]->op->c+=nf;
        }
    }

    void relabel(int p){
        cur[p]=ls[p];
        int Min=T+5;
        for (edge *t=ls[p];t;t=t->next)
            if (t->c && d[t->y]+1y]+1;
        d[p]=Min;
    }

    int sap(){
        Flow=0;
        for (int i=1;i<=T;i++){
            d[i]=0;
            Num[i]=0;
            cur[i]=ls[i];
        }
        Num[0]=T;
        int i=S;
        while (d[S]<=T){
            edge *&t=cur[i];
            for (;t;t=t->next)
                if (t->c && d[t->y]+1==d[t->x]) break;
            if (t){
                fa[t->y]=t;
                i=t->y;
                if (i==T){
                    change();
                    i=S;
                }
            }
            else{
                if ( (--Num[d[i]])==0 ) break;
                relabel(i);
                Num[d[i]]++;
                if (i!=S) i=fa[i]->x;
            }
        }
        return Flow;
    }
    
}Network;

int main(){
    while (scanf("%d",&n)!=EOF){
        Hash.clear();
        Ref.clear();
        for (int i=1;i<=n;i++){
            scanf("%d",&mat[i][0]);
            scanf("%d%d",&Out[i],&Out[i]);
            for (int j=1;j<=mat[i][0];j++){
                scanf("%d",&mat[i][j]);
                Hash.insert(mat[i][j]);
            }
        }
        int X;
        scanf("%d",&X);
        m=n;
        for (set::iterator it=Hash.begin();it!=Hash.end();it++) Ref[*it]=++m;
        for (int i=1;i<=n;i++)
            for (int j=1;j<=mat[i][0];j++)
                mat[i][j]=Ref[mat[i][j]];
        S=m+1; T=m+2;
        Network.clear();
        for (int i=1;i<=n;i++){
            Network.addedge(S,i,(i==X)?INF:Out[i]);
            for (int j=1;j<=mat[i][0];j++)
                Network.addedge(i,mat[i][j],1);
        }
        for (int i=n+1;i<=m;i++) Network.addedge(i,T,1);
        printf("%d\n",Network.sap());
    }
}

Help Me Escape(ZOJ 3640)
一只吸血鬼，有n条路给他走。每次他随机走一条路，每条路有个限制，如果当时这个吸血鬼的攻击力大于等于某个值，那么就会花费$$t_i$$天逃出去，否则，花费1天的时间，并且攻击力增加$$c_i$$。问他逃出去的期望。
$$p_{att}$$表示攻击力为att时的期望，$$p_{att} = frac{sum_{i=1}^n w_i}{n} $$，若$$att geq c_i$$，$$w_i = t_i$$，否则$$w_i = p_{att + i} + 1$$。

输出$$p_f$$
#include 
#include 
#include 
#include 
const int N=10005*2;
int n,f;
int c[105];
int T[105];
int v[N];
double F[N];

double gao(int att){
       if (v[att]) return F[att];
       v[att]=1;
       F[att]=0;
       for (int i=1;i<=n;i++)
           if (att>c[i]) F[att]+=T[i];
                    else F[att]+=gao(att+c[i])+1;
       F[att]/=n;
       return F[att];
}

int main(){
    while (scanf("%d%d",&n,&f)!=EOF){
          for (int i=1;i<=n;i++) scanf("%d",&c[i]);
          for (int i=1;i<=n;i++) T[i]=(int)((1+sqrt(5))*0.5*c[i]*c[i]+1e-8);
          memset(v,0,sizeof(v));
          printf("%.3lf\n",gao(f));
    }
}


Cinema in Akiba(ZOJ 3635)
有n个从1..n标号的座位，按时间顺序给出每个客人来的时候是坐在第几个空座位，最后给若干个询问问第i号客人坐在哪里。
每次二分加树状数组可以判定当前位置是第几个空座位。这个比线段树应该好写得多。复杂度$$O(n log^2 n)$$
#include 
#include 
#include 
#include 
using namespace std;
const int N=50005;
int n;
int Tr[N];
int P[N];

void Add(int i,int x){ 
	for (;i<=n;i+=i&-i) Tr[i]+=x; 
}

int Get_Sum(int i){
	int ret=0;
	for (;i;i-=i&-i) ret+=Tr[i];
	return ret;
}

int main(){
	while (scanf("%d",&n)!=EOF){
		for (int i=1;i<=n;i++) Tr[i]=0;
		for (int i=1;i<=n;i++) Add(i,1);
		for (int i=1,x;i<=n;i++){
			scanf("%d",&x);
			int l=1,r=n;
			while (l>1;
				if (Get_Sum(mid)>=x) r=mid;
				                else l=mid+1;
			}
			P[i]=l;
			Add(l,-1);
		}
		scanf("%d",&n);
		for (int i=0,x;i
Fruit Ninja(ZOJ 3638)
给定n个变量，第i个变量要么要求$$x_i \textless a_i$$，要么要求$$ x_i \textgreater a_i $$ ，问凑出s个水果并符合条件的方案数有多少种。
容斥原理，对于大于的限制，在s里面减就好了，对于小于的限制，就枚举破坏规则的mask，用容斥原理算，最后统计的部分用隔板法可以知道是一个组合数。因为模的数是素数，可以直接乘分母的逆元。
#include 
#include 
#include 
#include 
using namespace std;
const int N=25;
const int Mod=100000007;

int Power(int x,int cf){
    if (cf==0) return 1;
    long long ret=Power(x,cf>>1);
    ret=ret*ret%Mod;
    if (cf&1) ret=ret*x%Mod;
    return ret;
}

long long C(int m,int n){
    if (n<0 || n>m || m<0) return 0;
    long long up=1;
    long long down=1;
    for (int i=m-n+1;i<=m;i++) up=up*i%Mod;
    for (int i=1;i<=n;i++) down=down*i%Mod;
    return up*Power(down,Mod-2)%Mod;
}

int n,m,s;
char Str[100];
char S1[100];
char S2[100];
int a[N];
long long ans;

void dfs(int p,int sum,int t){
     if (sum<1) return;
     if (p>m){
        if (t&1) ans-=C(sum-1,n-1);
            else ans+=C(sum-1,n-1);
        ans=(ans%Mod+Mod)%Mod;
        return;
     }
     dfs(p+1,sum,t);
     dfs(p+1,sum-a[p],t+1);
}

int main(){
    while (scanf("%d%d",&n,&s)!=EOF){
        if (n==0) break;
        gets(Str);
        m=0;
        s+=n;
        bool check=true;
        while (1){
              if (!gets(Str)) break;
              if (strlen(Str)<2) break;
              int Num;
              sscanf(Str,"%s%s%s%d",S1,S1,S2,&Num);
              Num++;
              if (S1[0]=='l'){
                a[++m]=Num-1;
                if (Num==1) check=false;
              }
              else
                s-=Num;
        }
        if (!check) printf("0\n");
        else{
                ans=0;
                dfs(1,s,0);
                printf("%d\n",ans);
        }
    }
}


Education Manage System(ZOJ 3637)
给定若干门课的占用时间区间，问最多能选多少学分的课。
先把那些时间都化为分钟，然后这个时刻点最多不到60W，离散化都不用，直接dp就好了。$$f_i$$表示第i个时刻结束的时候，所能取得的最大学分。$$f_i = max (f_{i-1}, f_{st_k} + w_k)$$，其中$$ed_k = i$$。有两个trick：2012年是闰年以及课不能连续上，至少间隔5分钟。
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template  void checkmin(T &t,T x){if (x < t) t = x;}
template  void checkmax(T &t,T x){if (x > t) t = x;}
template  void _checkmin(T &t, T x){if (t == -1) t = x; if (x < t) t = x;}
template  void _checkmax(T &t, T x){if (t == -1) t = x; if (x > t) t = x;}
typedef pair  PII;
typedef pair  PDD;
typedef long long lld;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
#define DEBUG(a) cout << #a" = " << (a) << endl;
#define DEBUGARR(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
const int N = 100005;
const int M = 600005;
const char Mon[12][4] = {"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"};
const int ms[12] = {0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335};
int n;
double w[N];
PII a[N];
char buf[200];
double f[M];
vector  E[M];

int getMonth() {
	scanf("%s", buf);
	for (int i = 0; i < 12; i++) {
		if (!strcmp(buf, Mon[i])) {
			return i;
		}
	}
}

int getDay() {
	int x;
	scanf("%d%s", &x, buf);
	return x;
}

int getTime() {
	int month = getMonth();
	int day = getDay();
	int hour, minute;
	scanf("%d:%d %s", &hour, &minute, buf);
	if (buf[0] == 'p') {
		hour += 12;
	}
	return (ms[month] + day) * 24 * 60 + hour * 60 + minute + 1; 
}

int main(){
#ifdef cwj
	freopen("in", "r", stdin);
#endif
	while (scanf("%d", &n) != EOF) {
		for (int i = 0; i < M; i++) E[i].clear();
		for (int i = 0; i < n; i++) {
			a[i].first = getTime();
			a[i].second = getTime();
			a[i].second += 5;
			E[a[i].second].push_back(i);
			scanf("%lf", &w[i]);
		}
		memset(f, 0, sizeof(f));
		for (int i = 1; i < M; i++) {
			f[i] = f[i - 1];
			foreach (it, E[i]) {
				checkmax(f[i], f[a[*it].first] + w[*it]);
			}
		}
		printf("%.1lf\n", f[M - 1]);
	}
}


Keep Deleting(ZOJ 3643)
给定串A和串B。每次从左往右看，如果发现A作为B的substring出现，那么删掉A，对新串递归进行这个操作，问你删到不能删为止，删了多少次。
先算出串A在KMP里的next函数，然后从前往后扫B串，用一个栈维护仍未被删掉，但是已经被扫描过的字符。如果KMP匹配上，那么把栈顶的A.size()个字符退栈，KMP的匹配位置回档到栈顶的元素的匹配位置。这样一直下去计算退栈次数即可。

我的代码比较奇怪，用Disjoint Set的方式替代了栈...用栈的复杂度是$$O(n)$$的。
#include 
#include 
#include 
#include 
using namespace std;
const int N=512005;
int m,n;
int next[N];
int Pre[N];
int Now_j[N];
int v[N];
char A[N];
char B[N];

int Get_Pre(int p){
    if (p==0 || !v[p]) return p;
    return Pre[p]=Get_Pre(Pre[p]);
}

int main(){ 
    while (scanf("%s%s",A+1,B+1)!=EOF){
        m=strlen(A+1);
        n=strlen(B+1);
        next[1]=0;
        int j=0;
        for (int i=2;i<=m;i++){
            while (j && A[j+1]!=A[i]) j=next[j];
            if (A[j+1]==A[i]) j++;
            next[i]=j;
        }
        j=0;
        int ans=0;
        for (int i=1;i<=n;i++) Pre[i]=i-1;
        for (int i=0;i<=n;i++) v[i]=0;
        for (int i=1;i<=n;i++){
            while (j && A[j+1]!=B[i]) j=next[j];
            if (A[j+1]==B[i]) j++;
            Now_j[i]=j;
            if (j==m){
                ans++;
                int k=i;
                for (int t=0;t
Guess a Function(ZOJ 3639)
让你根据sample的数据猜4个参数m1,s1,m2,s2，他们的范围都小于等于345678，并且0.3m1 < s1 < m1, 0.3m2 < s2 < m2

zYc出的神题。g(x)的本质是x ^ (x >> 1)，所以这个反函数也是可以求的...就是类似逐差法，知道最高位和接下来这位的异或值，然后一步一步推下来就可以求得。

然后自然地就想到枚举s1, m1。然后求对应的s2, m2(因为如果枚举两个m，或者两个s，中间都要经过g的运算，有了位运算和这种加减混合是不好求的)。
那么现在相当于知道n组数据a[i],b[i]满足b[i] = a[i] * m2 / m2 + (a[i] + s2) % m2，求m2, s2。其实这个这么复杂的运算也就是a[i] + s2 = b[i]和a[i] + s2 - m2 = b[i]这两种情况。而且后者满足b[i] < a[i]... 所以只要找一个a[i] < b[i]，一个a[i] > b[i]的就可以解出m2, s2了...再test一下是否满足全部即可。

当然虽然思路是这样，但是写起来在常数上还是很有技巧的。像猛犸学长写的只需要3分钟就能跑出这4个参数。我的要跑1个多小时就不放了...
/* 解题报告 //

给出三个函数，分别是
g(x) = x xor (x / 2)
h1(x) = x / m1 * m1 + (x + s1) % m1
h2(x) = x / m2 * m2 + (x + s2) % m2
数据给出许多 x，求对应 f(x) = g(h2(g(h1(g(x))))) 的函数值

g(x) 实质是序号转格雷码的函数，是一一对应函数，因此它有反函数 h(x)
h(x) 比较复杂，可以用循环一个个处理，也可以像我的程序里那样写

有了 g(x) 和 h(x) 之后，就可以对输入数据和输出数据进行处理
把原函数最内层和最外层的 g(x) 去掉，变成 f'(x) = h2(g(h1(x)))

但是 h2(g(h1(x))) 这玩意还是很难处理，于是暴力破解之
枚举 h1 的两个参数 s1 和 m1，然后进一步处理输入数据，再去掉 g(h1(x))
得到 f''(x) = h2(x) = x / m2 * m2 + (x + s2) % m2

对 h2(x) 进行简单的表达式化简，可以得到
   h2(x) = x / m2 * m2 + (x + s2) % m2
         = x - x % m2 + (x % m2 + s2) % m2
         = x + s2       (当 x % m2 + s2 <  m2 时)
    或者 = x + s2 - m2  (当 x % m2 + s2 >= m2 时)

对于所枚举的 s1 和 m1，检查每一对输入输出数据 u[i] 和 v[i]，
如果 v[i] > u[i]，则 v[i] = u[i] + s2
如果 v[i] < u[i]，则 v[i] = u[i] + s2 - m2
当然，如果 v[i] == u[i] 则枚举的 s1 和 m1 是非法的
根据上面的式子，可以唯一地计算出 s2 和 m2 的值
当然，若 s2 或 m2 不唯一，则说明枚举的 s1 和 m1 也是非法的

在暴力尝试所有 s1 和 m1 的组合之后
只有 s1 = 100007, m1 = 214748 是合法的
对应 s2 = 123123, m2 = 201263

// By 猛犸也钻地 @ 2012.07.19 */

#include 

unsigned g(unsigned x){return x^x>>1;}
unsigned h(unsigned x){return x^=x>>16,x^=x>>8,x^=x>>4,x^=x>>2,x^x>>1;}

unsigned u[6000],v[6000],x,i,n,s1,m1,s2,m2,w2;

void gao(){
    FILE* dat=fopen("dat","r"),* ans=fopen("ans","r");
    for(n=0;fscanf(dat,"%u",&x)==1;u[n++]=g(x));
    for(n=0;fscanf(ans,"%u",&x)==1;v[n++]=h(x));
    for(m1=1;m1<=345678;m1++)
    for(s1=1+m1*3/10;s1=m1?s1-m1:s1)+u[i]);
            if(v[i]==x) break;
            if(v[i]> x){
                if(!s2) s2=v[i]-x; else if(s2!=v[i]-x) break;
            }else{
                if(!w2) w2=v[i]-x; else if(w2!=v[i]-x) break;
            }
        }
        if(i==n) printf("%u %u %u %u\n",s1,m1,s2,s2-w2);
    }
}

int main(){
    s1=100007,m1=214748,s2=123123,m2=201263;
    while(scanf("%u",&x)==1){
        x=g(x);
        x=g(x-x%m1+(x%m1+s1)%m1);
        x=g(x-x%m2+(x%m2+s2)%m2);
        printf("%u\n",x);
    }
}

加入对话

19条评论

匿名说：

26 8 月, 2012 5:51 下午

..

回复
1. edward_mj说：
  
  26 8 月, 2012 8:34 下午
  
  :Amazed:
  
  回复
fancy说：

26 8 月, 2012 8:46 下午

仰慕写解题报告的学长
BG吧！

回复
prowindy说：

26 8 月, 2012 10:01 下午

继承shi哥意志继续操刀月赛题解的MJ桑~

回复
HJWAJ说：

27 8 月, 2012 12:45 上午

手算了两个小时G最后剪枝错了没搞出来的表示泪奔。。。

回复
匿名说：

27 8 月, 2012 4:45 下午

orz

回复
ZeroClock说：

27 8 月, 2012 6:05 下午

Bounty Hunter(ZOJ 3634)这题，不知道以下想法是否可行：
因为每次选择增加攻击力，对之前的状态都没影响，而是对之后的状态有影响，那就将对后面的影响考虑进来，后面全部的bi相加为sum，当前有的钱为money，可知在当前城市若增加攻击力，对后面的影响为money / ai * sum，那我们只要判断ai和sum大大小关系就可以决定在当前城市是否增加攻击力。还有一点，如果选择增加攻击力，那肯定是把钱全部用来增加攻击力，然后再换钱。

我想了两种方法，一种和解题报告的相似，一种就是上面描述的。我自己出的20多组数据答案都一样，可上面描述的方法就是Wa，也wa了20几次了

回复
1. edward_mj说：
  
  28 8 月, 2012 6:50 下午
  
  你要考虑到后面加的钱还可以重复利用。也就是说那些多出来的钱还要用来换新的攻击力的。
  
  回复
  1. 匿名说：
    
    28 8 月, 2012 10:20 下午
    
    这个我有考虑，因为前面增加的攻击力不会减少，那么对后面的影响可以提前算出。当每次决策时，就用全部的钱减去前面的攻击力和钱对后面的影响，就得到当前用的钱，然后判断要不要买攻击力，要的话又继续算出对后面的影响。额，感觉说不清楚，能不能发一些数据到我邮箱:353230424@qq.com？
    
    回复
    1. edward_mj说：
      
      28 8 月, 2012 10:44 下午
      
      ZOJ数据是必须保密的…
      其实我感觉你这个和我的思路应该差不多的啊。你要算出有多少影响，就必须考虑到钱怎么花才最好。这本身就要一个贪心的过程…
      
      回复
      1. ZeroClock说：
        
        29 8 月, 2012 2:22 下午
        
        那悲剧了，应该也不是精度问题。咳，自己出数据对拍吧…
        
        回复
ftiasch说：

27 8 月, 2012 10:30 下午

换个latex插件吧。这个看上去难看死了。

回复
1. ftiasch说：
  
  27 8 月, 2012 10:30 下午
  
  居然还是图片……
  
  回复
  1. edward_mj说：
    
    27 8 月, 2012 10:50 下午
    
    我觉得这个除了有点下沉以外还好啊，你的那个在firefox下是很漂亮，但是在windows默认设置的chrome里那些字体都发虚…图片不容易出这个问题= =|||
    
    回复
_LT_zyc说：

5 9 月, 2012 6:32 下午

ZOJ 3634 这题数据有点问题？
int main(){
// freopen(“e:\in.txt”,”r”,stdin);
while(scanf(“%d%lf%lf”,&n,&X,&Y)!=EOF){
for(i=1;i=1;i–){
double k=(b[i+1]/x[i]+y[i]*a[i+1]/x[i]-a[i+1]);
double b1=a[i+1];
if(k<0) a[i]=b1;
else a[i]=k+b1;
b[i]=y[i]*a[i+1]+b[i+1];
if(i==n&&a[i]!=max((double)1,y[n]/x[n])) while(1){}
//这句话本来用来检测一下我代码初始化的问题，应该没什么影响，但加上去AC，不加会WA，这个。。。搞不懂了
}
printf("%.2lfn",X*a[1]+Y*b[1]);
}
return 0;
}

回复
1. edward_mj说：
  
  5 9 月, 2012 6:55 下午
  
  你的代码太不完整了…. 而且这是什么… “for(i=1;i=1;i–){”
  这样我没法判断是哪边的问题
  
  回复
  1. _LT_zyc说：
    
    5 9 月, 2012 8:21 下午
    
    哦，这里格式好像有问题
    这是AC代码的链接
    http://acm.hust.edu.cn:8080/judge/contest/viewSource.action?id=668944
    WA代码的链接
    http://acm.hust.edu.cn:8080/judge/contest/viewSource.action?id=668940
    两份代码就差了刚刚那一句
    if(i==n&&a[i]!=max((double)1,y[n]/x[n])) while(1){}
    看一下吧，谢谢
    
    回复
    1. edward_mj说：
      
      5 9 月, 2012 9:00 下午
      
      同学, 很抱歉地通知您, 你的代码在我本机跑, 不加O2是通过的.
      加了O2, 你的某组case和答案差0.01.
      大概是除法造成的精度损失比较大, 而我们又有0.005附近的数据, 所以跪了.
      我试了下, 改成long double 也无济于事…
      而你加了那句话以后, 那部分代码有死循环, O2就不作优化了… 于是就过了.
      
      回复
      1. _LT_zyc说：
        
        5 9 月, 2012 9:02 下午
        
        饿，好吧我错了，谢谢啦
        
        回复

[题解]ZOJ Monthly, August 2012

加入对话

留下评论

取消回复