分类存档：默认分类

呓语

首先恭喜shi哥SRM 554夺冠！
然后是对自己的吐槽
这两天下来CF和TC都跌惨了…
CF: 2285 -> 2237
TC: 1955 -> 1913
和以前很不一样, 这回跌了没有觉得特别失落.
不知道我的心态是从什么时候开始改变的.
现在好像跪掉什么东西, 不影响生活的, 都没有多大感觉.
嘛, 不过是漫长的人生里的一段经历罢了.
突然想起以前做过的一些糊涂事.
比如说, CF大号红了就换小号做了.
现在想起来, 真是可笑.
不是说不可以,这本质就是不自信…
或者说, 就是虚.
哈哈，暑假集训和徒弟打了好多把dota, 我经常团战和gank的时候都比较猥琐, 天天都被徒弟喷虚 :I-see-stars:
现在没什么这种感觉了, 总觉得, 要是在这个rating就止步, 那也圡了.
难道自己真的就只有这种水准么.
然后嘛，虽然感觉没什么特别失落，还是总结一下这两场的情况。
codeforces 136
A 真的是脑子抽, 15分钟虽然有点对不起观众, 但是还算没有梦游到没底.
B 一开始算错数, 写了个块状数组, 然后WA了, 然后发现过来以后推倒重写了个树状数组的, 过掉了还算正常吧.
C 本来是20分钟内轻松过的题啊, 然后答案是按shift left顺序, 我写成了shift right顺序, 关键sample还是对称的… 临近结束才察觉不对劲, 遂fix之.
然后E题超级水啊-.- D题也不难.若是C题别那么圡, 出掉E题应该还是要不大的.

SRM 554
250 手速还算可以…
500 很快推出了答案是先递减后递增的情形, 但是居然没想到用递归去实现. 然后就写了好久好久， 最后还因为没有判断heights.size() == 1的情况fail掉了.

总结起来, 出idea的速度还是很对得起自己的rating的, 总是实现代码的时候各种犯2.
sigh, 其实一年前, 饮恨regional也是这个原因.
时至今日, 仍然如此.
可见人圡没有药可医啊.
其实就是那种很不太在状态的感觉, 多刷点水题似乎能有效改善这种状况.
希望在regional前调整过来吧.
明天(其实是今天吧)去买双新的板鞋好了, 老是穿运动鞋好单调啊.
虽然说是男孩子, 但是有时候也要理一理, 卖弄一下风骚对吧~ :Smile:
于是睡觉去.

[题解]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);
    }
}

随笔

  1. 很无聊地骑着自行车在校园里逛了一圈，看着穿着求是服 || 军服的学弟学妹不禁感叹，哎呀，大一就这么过去了呢。看着校园里忙碌的身影，心里突然冒出这么一句话：努力不是为了向别人表现什么，只是不想让别人在我面前展示赤裸裸的真实。
  2. 说说集训吧
    组队集训已经打了有11场左右了，总的来说集训成绩还是很不错的，似乎不怎么比上一年的1队弱吧。队友都挺给力，基本上现场有2个队过的题目，我们至少都是有靠谱想法的。但是手速是个大问题，我的手速算是比较快的，prowindy比较正常，而zYc就比较慢…这样的节奏导致我们基本上每次可做题都没做完，比赛就结束了。这种情况我也不知道要怎么办，毕竟手速不是一朝一夕的事情。本来今年不想在1队混,但是在prowindy的诱拐以及各种各样奇怪的因素下，还是做了1队队长 :Weary:实际上我是个缺乏领导力的人，看到数据机构题、图论题什么的就很不怕死地跑上去搞，所以我们队的任务分工主要还是由经验老道的prowindy同学执行。既然不这样都这样了，就只能用力搞了吧。吐槽：发现自己真是个心软的人啊，只要不是太坑爹的情况，就挡不住别人的请求…
  3. 昨天和猛犸等去吃饭，讨论起当时组队的事情。发现原来想去final的人有很多，如果我不在1队的话，组队反而就好办得多，但是当时又跑去了VK CUP，大家都以为我很想去final，于是乎就成了现在这个状况了。仔细数数真是坑了不少人…席间又说到今年的情况，我说了一句，我们队应该还是能和别人家的2队刚的吧。然后被猛犸呸了一脸。 :Sad: 确实啊，这点自信都没有，真是搞毛线…
  4. 关于我们奇葩的队名
    来历是prowindy觉得取A开头的字典序比较小，于是我答复了一个Arcadia，然后prowindy又要求凑一个大写的C，凑出AC来。于是翻了翻字典，-.-，Convent出现在我的眼前。于是乎两个拼接在一起，就成了似乎具有里番色彩的ArcadiaConvent了。大概这要成为ZJU 1队史上最奇葩队名了吧 :Beer:
  5. 昨天是七夕吧，又想起了一些事情。不管怎么样，都过去了。吃一堑长一智，感谢你让我变得成熟。但也就这样吧。

新blog落成

建这个Blog有这个几个原因：

1、百度的那个换新版了以后简直不能用啊！

2、很久没有写blog了，最近集训有些想写的东西。

3、以前对网络的各种东西完全是一无所知，但是上学期上了无线网络与应用，对一些网络概念有了最圡的认识。现在想实践了一下…

于是乎，昨天跑去ucvps租了个vps，配置了一下，装上了ubuntu11.04，然后今天去万网注册了这个域名。按部就班地配lnmp，ftp，mysql，php，wordpress，在犯了无数不能忍的错误之后，终于配好了…不容易啊T_T，于是纪念一下。