【日常小测】三明治

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/07/20170623_statement.pdf

解题报告

假如我们钦定某个格子先取走靠左的三角形,那么其余格子是先取走靠左还是靠右就全部定下来了
于是我们暴力枚举一下,复杂度是$O(n^4)$

更进一步,我们发现:

假如我们钦定先取走$(x, y)$这个格子的靠左三角形
那么我们一定得先将$(x – 1, y)$这个格子的左三角形取走,然后再取走一些其他的三角形

于是同一行的信息是可以共用的,然后就可以记忆化搜索了
时间复杂度是$O(n^3)$的

Code

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

const int N = 500;
const int INF = 1e7;

char mp[N][N];
int n, m, ans[N];
bool up[N][N], dw[N][N], InStack[N][N], vis[N][N];

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

inline int F(int x, int y, int t) {
	InStack[y][x] = 1;
	int nx = x + (t == 1? 1: -1), ny = y, nt = t, ret = 1;
	ret += vis[ny][nx]? 0: (InStack[ny][nx]? INF: F(nx, y, t));
	nx = x; ny = up[y][x] == t? y - 1: y + 1; nt = up[y][x] == t? up[ny][nx]: dw[ny][nx];
	ret += vis[ny][nx] || ret >= INF? 0: (InStack[ny][nx]? INF: F(nx, ny, nt));	
	vis[y][x] = 1;
	InStack[y][x] = 0;
	return ret > INF? INF: ret;
}

inline void init() {
	memset(vis, 0, sizeof(vis));
	for (int j = 1; j <= m; j++) {
		vis[j][0] = 1;
		vis[j][n + 1] = 1;
	}
	for (int i = 1; i <= n; i++) {
		vis[0][i] = 1;
		vis[m + 1][i] = 1;
	}
}

int main() {
	m = read(); n = read();
	for (int j = 1; j <= m; j++) {
		scanf("%s", mp[j] + 1);
		for (int i = 1; i <= n; i++) {
			up[j][i] = 1;
			dw[j][i] = 0;
			if (mp[j][i] == 'Z') {
				swap(up[j][i], dw[j][i]);
			}
		}
	}
	for (int j = 1; j <= m; j++) {
		init();
		for (int i = n; i; i--) {
			ans[i] = ans[i + 1] < INF? F(i, j, 1) + ans[i + 1]: INF;
		}
		init();
		for (int i = 1; i <= n; i++) {
			ans[i] = min(ans[i], ans[i - 1] < INF? F(i, j, 0) + ans[i - 1]: INF);
			printf("%d ", ans[i] >= INF? -1: ans[i] << 1);
		}
		putchar('\n');
	}
	return 0;
}

【BZOJ 2471】Count

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2471
神犇题解:http://www.cnblogs.com/clrs97/p/5993606.html

解题报告

我们考虑从高位开始,逐位枚举。那么每枚举一位相当于将序列划分为10分,并且取其中一份。
对于一段连续的序列来讲,我们只需要关注其进入这段序列之前会匹配到x的哪一位、匹配完这一段之后匹配到了x的哪一位、这期间总共贡献了多少次成功的匹配。
不难发现这个状态是很少的,于是我们可以记忆化搜索。

另外这题很容易扩展到:“左右边界为任意值的情况”
然后我把这题搬到了今年的全国胡策里,不知道有没有人能切掉

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 16;
const int M = 10;
const int SGZ = 10;
const int MOD = 1000000007;
 
int n, m, nxt[M];
char s[M];
struct Transfer{
    LL pos, cnt;
    inline Transfer() {
    }
    inline Transfer(LL a, LL b):pos(a), cnt(b) {
    }
    inline Transfer operator + (const Transfer &T) {
        return Transfer(T.pos, cnt + T.cnt);
    }
}t[M][SGZ];
map<int, Transfer> f[N][M];
struct MatchStatus{
    int HashVal;
    Transfer t[M];
    inline void GetHashVal() {
        const static int MOD = 1000000007;
        const static int SEED1 = 13, SEED2 = 131;
        HashVal = 0;
        for (int i = 0; i < m; i++) {
            HashVal = (HashVal + (LL)t[i].pos * SEED2 + t[i].cnt) * SEED1 % MOD;
        }
    }
    inline bool operator < (const MatchStatus &MS) const {
        return HashVal < MS.HashVal;
    }
};
 
inline Transfer DFS(int w, int p, const MatchStatus &cur) {
    if (w <= 0) {
        return cur.t[p];
    } else if (f[w][p].count(cur.HashVal)) {
        return f[w][p][cur.HashVal];
    } else {
        Transfer ret(p, 0);
        for (int i = 0; i < SGZ; i++) {
            MatchStatus nw = cur;
            for (int j = 0; j < m; j++) {
                nw.t[j] = nw.t[j] + t[nw.t[j].pos][i];
            }
            nw.GetHashVal();
            ret = ret + DFS(w - 1, ret.pos, nw);
        }
        return f[w][p][cur.HashVal] = ret;
    }
}
 
int main() {
    while (~scanf("%d %s", &n, s + 1) && n) {
        m = strlen(s + 1);
        for (int i = 1; i <= m; i++) {
            s[i] -= '0';
        }
        nxt[1] = 0;
        for (int i = 2, j = 0; i <= m; nxt[i++] = j) {
            for (; j && s[j + 1] != s[i]; j = nxt[j]);
            j += s[j + 1] == s[i];
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < SGZ; j++) {
                int k = i;
                for (; k && s[k + 1] != j; k = nxt[k]);
                k += s[k + 1] == j;
                t[i][j] = k == m? Transfer(nxt[k], 1): Transfer(k, 0);
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < m; j++) {
                f[i][j].clear();
            }
        }
        Transfer ans(0, 0);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < SGZ; j++) {
                MatchStatus cur;
                for (int k = 0; k < m; k++) {
                    cur.t[k] = t[k][j];
                }
                cur.GetHashVal();
                ans = ans + DFS(i - 1, ans.pos, cur);
            }
        }
        printf("%lld\n", ans.cnt);
    }
    return 0;
}

【TopCoder SRM713】PowerEquation

相关链接

题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=14573&rd=16882

题目大意

给定$n(n \le 10^9)$,问有多少组不同的$a^b=c^d$成立
要求$1 \le a,b,c,d \le n$

解题报告

假设$a^b=c^d$,我们在枚举到$gcd(a,c)$的时候计算
如果$gcd(a,c)=a=c$的话,贡献显然是$n$
所以我们枚举$gcd$只需要枚举到$\sqrt{n}$
又因为次数非常小,所以我们可以暴力算有多少种指数满足要求
于是总的复杂度大概是$\sqrt{n}$的

Code

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

const int MOD = 1000000007;
const int N = 100000;

int gcd[100][100];
bool vis[N];

class PowerEquation {
    public:
    	int count(int n) {
    		memset(vis, 0, sizeof(vis));
    		for (int i=1;i<=50;i++) {
				for (int j=1;j<=50;j++) {
					gcd[i][j] = GCD(i, j);
				}
			}
			
			int ret = (LL)n * n % MOD, dec = 0;
    		for (int i=2;1;i++) {
				if (i * i > n) {
					ret = (ret + (n - i + 1ll - dec) * n) % MOD;
					break;	
				} else {
					if (vis[i]) continue;
					for (LL j=i*i;j<=n;j*=i) {
						if (j * j <= n) vis[j] = 1;
						else ++dec;
					}
					
					int mx = 1, tmp = 0; LL cur = i;
					while (cur * i <= n) cur *= i, ++mx;
					for (int a=1;a<=mx;a++) {
						for (int b=1;b<=mx;b++) {
							int c = max(b,a) / gcd[a][b];
							tmp = (tmp + n / c) % MOD;
						}
					} 
					ret = (ret + tmp) % MOD;
				}
			}
    	    return ret;
   		}
   	private:
   		int GCD(int a, int b) {
			return b? GCD(b, a%b): a;   
		}
};

【BZOJ 4801】打牌

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4801

解题报告

大暴搜游戏题
复杂度:$O(4T)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
int a[5][5],cur[3][3];
 
inline int read() {
    char s[5]; scanf("%s",s);
    if (s[0] == 'A') return 14;
    if (s[0] == 'K') return 13;
    if (s[0] == 'Q') return 12;
    if (s[0] == 'J') return 11;
    if (s[0] == 'T') return 10;
    return s[0] - '0';
}
 
inline int val(int x) {
    if (x == 14) return 1;
    else return x; 
}
 
int solve(int t) {
    if (t == 1) {
        cur[0][0] = a[0][0]; cur[0][1] = a[0][1];
        int s1 = solve(2); 
        swap(cur[0][0], cur[0][1]);
        int s2 = solve(2);
        return max(s1, s2);  
    } else if (t == 2) {
        cur[1][0] = a[1][0]; cur[1][1] = a[1][1];
        int s1 = solve(3);
        swap(cur[1][0], cur[1][1]);
        int s2 = solve(3);
        return min(s1, s2);
    } else {
         if (cur[0][0] >= cur[1][0]) {
            if (cur[0][1] >= cur[1][1]) {
                return val(cur[0][0]) + val(cur[0][1]);
            } else {
                return val(cur[0][0]) - val(cur[1][1]);
            } 
         } else {
            if (cur[0][1] > cur[1][1]) {
                return -val(cur[1][0]) + val(cur[0][1]);    
            } else {
                return -val(cur[1][0]) - val(cur[1][1]) ;
            }
         }
    }
}
 
int main() {
    int t; cin>>t; 
    for (;t;t--) {
        a[0][0] = read(); a[0][1] = read();
        a[1][0] = read(); a[1][1] = read();
        printf("%d\n",solve(1));
    }
    return 0;
}

【TopCoder SRM712】LR

相关链接

题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=14569&rd=16881

解题报告

我们经过观察发现,操作顺序不影响结果
于是我们就可以暴力枚举多少个$L$多少个$R$然后暴力判断
时间复杂度:$O(n \log^2 10^{17})$

Code

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

class LR {
    public:
    	string construct(vector<long long> s, vector<long long> t) {
    	    int n=s.size(),SPJ=1; LL s1=0,s2=0,pp,cnt=0;
    	    for (int i=0;i<n;i++) s1 += s[i], s2 += t[i], SPJ = (t[i]!=s[i]?0:SPJ);
    	    if (SPJ) return ""; pp = s1;
    	    if (s2-s1 <= 0 || (!s1 && s2)) return "No solution";
    	    while (pp<s2) pp<<=1,++cnt; 
			if (pp != s2) return "No solution";
			for (int i=0;i<=cnt;i++) {
				if (judge(s, t, i, cnt-i)) {
					string ret="";
					for (int j=1;j<=i;j++) ret += "L";
					for (int j=i+1;j<=cnt;j++) ret += "R";
					return ret;
				}
			}
			return "No solution";
   		}
   	private:
   		inline bool judge(vector<LL> s, vector<LL> t, int L, int R) {
			LL tmp[55],a[55],b[55],n=s.size();
			for (int i=1;i<=n;i++) a[i] = s[i-1], b[i] = t[i-1];
			for (int k=1;k<=L;k++) {
				for (int i=1;i<=n;i++) tmp[i] = a[i]; tmp[0] = a[n];
				for (int i=1;i<=n;i++) a[i] = tmp[i-1] + tmp[i];
			}
			for (int k=1;k<=R;k++) {
				for (int i=1;i<=n;i++) tmp[i] = a[i]; tmp[n+1] = a[1];
				for (int i=1;i<=n;i++) a[i] = tmp[i] + tmp[i+1];
			}
			for (int i=1;i<=n;i++) if (a[i] != b[i]) return 0;
			return 1;
		} 
};

【Codeforces 797E】Array Queries

相关链接

题目传送门:http://codeforces.com/contest/797/problem/E

解题报告

我们发现暴搜加上记忆化的复杂度是$O(n \sqrt{n})$的
于是暴搜就好了

Code

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

const int N = 100009;

struct Query{int p,k,id;}q[N];
int n,m,stp[N],a[N],ans[N];
queue<int> vis;

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;
}

inline bool cmp(const Query &A, const Query &B) {
	return A.k < B.k; 
}

inline void init() {
	for (;!vis.empty();vis.pop()) {
		stp[vis.front()] = 0;
	}
}

int DFS(int w, int k) {
	if (w > n) return 0;
	else if (stp[w] > 0) return stp[w];
	else return vis.push(w), stp[w] = DFS(w + a[w] + k, k) + 1;	
}

int main() {
	n = read(); for (int i=1;i<=n;i++) a[i] = read();
	m = read(); for (int i=1;i<=m;i++) q[i].p = read(), q[i].k = read(), q[i].id = i;
	sort(q+1, q+1+m, cmp);
	for (int i=1;i<=m;i++) {
		if (i > 1 && q[i].k != q[i-1].k) init();
		ans[q[i].id] = DFS(q[i].p, q[i].k);
	} 
	for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}

【BZOJ 4145】[AMPPZ2014] The Prices

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4145
神犇题解:http://blog.csdn.net/popoqqq/article/details/46547683

解题报告

先来说一个自己YY的暴力
枚举每一个合法集合,考虑这个集合的物品全部在某一个商店购买
如果我们把这些集合再拿来搞一搞组合,显然可以搞出来正确答案
使用背包DP的话,直接做复杂度是$O(4^m)$,考虑一点优化:
根据我们对于集合的定义,两个集合能够组合在一起,当且仅当两个集合没有交集
然后写个程序跑一跑,发现这种组合大概只会有4e7个,于是暴力搞一搞就好啦!
然后就垫底了 QwQ

现在考虑正解
刚刚我们其实是把整个商店买了哪些物品当作一个新物品,然后用新物品来进行背包DP
考虑我们直接把商店里面的物品拿来做背包DP会有什么问题:商店本身的花费$d_i$不好整
于是我们分阶段来背包DP,每一个商店一个阶段。
在这个阶段中,我们给所有状态加上这个商店的花费$d_i$,表示我们钦定这个商店要买东西
然后把物品拿来做背包,最后再和上个阶段的对应状态取个$min$
然后就做完啦!时间复杂度: $O(nm{2^m})$

Code

贴的这份代码是我YY的暴力

#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));
	n = read(); m = read();
	for (int i=1,d;i<=n;i++) {
		d = read();
		for (int j=1;j<=m;j++) 
			cost[j] = read();
		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 ——————————
感觉使用以下代码来枚举子集可能会使我的暴力不那么接近于TLE:

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

【BZOJ 4059】[Cerc2012] Non-boring sequences

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4059
神犇题解Ⅰ:http://blog.csdn.net/popoqqq/article/details/46380617
神犇题解Ⅱ:http://krydom.com/bzoj4059/

解题报告

考虑直接找出所有不无聊的区间
直接 $ O(n^2)$ 枚举的话,会T掉,于是考虑分治
假如当前考虑到的区间为(l,r),且这个区间中一个只出现过一次的数为x,下标为p
那么显然,横跨x的区间合法,两边的区间就递归下去做就好啦!

但如果每一次我们从左到右扫描x的话,时间复杂度长这样:$ T(n) = T(n – 1) + n$
这样的话,上限是 $ O(n^2)$ 显然不清真
考虑同时从两边开始扫描的话,复杂度就变为了: $ T(n) = T(p) + T(n – p) + \min (n – p,p)$
于是这个是:$ O(n\log n)$ 的,于是就可以愉快的暴力啦!
至于复杂度的证明的话,我们发现这货的形式和线段树的启发式合并的式子长得一毛一样
因为线段树的启发式合并是 $ O(n\log n)$ 的,那么这货的复杂度也就是对的啦!

当然你也可以使用归纳法什么的来证明复杂度
甚至你可以根本不用这个暴力的算法,而使用优雅的矩形面积并来做:
http://www.cnblogs.com/DaD3zZ-Beyonder/p/5803964.html

【BZOJ 1053】[HAOI2007] 反素数ant

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1053
神犇题解:http://medalplus.com/?p=2105

题解

这种题看一眼就会去想找规律吧?
打个表看一看大概是这样:

于是我们可以找到如下规律:
1.质因数是连续的,也就是说我们只用考虑37及之前的质因数
2.较大的质因数个数一定少于较小的质因数的个数

于是我们就可以写个深搜
枚举出所有符合条件的数
然后用这些数去更新答案辣!

Code

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

const int SZ = 12;

int n,num,vout,pri[]={0,2,3,5,7,11,13,17,19,23,29,31,37};

inline int read(){
	char c=getchar(); int ret=0,f=1;
	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 DFS(int t, int last, int w, int v) {
	if (t == 13) {
		if (v == num) {
			vout = min(vout, w);
		} else if (v > num) {
			vout = w;
			num = v;
		}
	} else {
		for (int i=0,cur=1;i<=last;i++,cur*=pri[t]) {
			if ((LL)cur * w > n) break;
			else {
				DFS(t+1, i, w*cur, v*(i+1));
			} 
		}
	}
}
 
int main(){
	if ((n=read()) == 1) {
		puts("1");
	} else {
		DFS(1,30,1,1);
		printf("%d\n",vout);
	}
	return 0;
}

【BZOJ 4419】发微博

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4419
神犇题解:http://www.cnblogs.com/ziliuziliu/p/5470337.html

题解

我的想法是把关系修改扔到map里面去
然后log(n)的时间查询上一个修改是多久
这样问题就变成了询问时间l到r中点c进行了多少次+1操作
这个用主席树就可以了

然而看了题解之后发现,似乎用暴力搞就可以了?
用前缀和的思想:
关系建立的时候减去,关系解除时加回来
最后再用set处理一下剩下的就可以辣!