【AtCoder】[Regular Contest 075 F] Mirrored

相关链接

题目传送门:http://arc075.contest.atcoder.jp/tasks/arc075_d

解题报告

之前PKUSC的时候考过$n + rev(n) = d$的版本
所以这一次把暴搜重新打一次就过了

Code

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

int *mth, *spj, a2[100], a1[100]; 

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

LL DFS(LL res, LL l, LL r) {
	if (l <= r) {
		if (res == 0) {
			return l == r? 10: 1;
		} else {
			return 0;
		}
	} else {
		LL ret = 0, cur = l - r;
		l /= 10; r *= 10;
		for (int i = -9; i <= 9; i++) {
			if (abs(res - i * cur) < l * 11) {
				ret += mth[i] * DFS(res - i * cur, l, r);				
			}
		}
		return ret;
	}
}

int main() {
	mth = a1 + 50;
	spj = a2 + 50;
	for (int i = 0; i <= 9; i++) {
		for (int j = -9; j <= 0; j++) {
			mth[i + j]++;
		}
	}
	for (int i = 1; i <= 9; i++) {
		for (int j = -9; j <= 0; j++) {
			spj[i + j]++;
		}
	}
	LL ans = 0, D = -read();
	for (LL mx = 1e18; mx >= 10; mx /= 10) {
		LL delta = mx - 1;
		for (int i = -8; i <= 9; i++) {
			ans += spj[i] * DFS(D - i * delta, mx / 10, 10);
		}
	}
	cout<<ans<<endl;
	return 0;
}

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

【BZOJ 3990】[SDOI2015] 排序

相关链接

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

解题报告

最开始一眼看成神题,还在想$SDOI$这是要赶超$ZJOI$的节奏啊
然后就发现看漏条件了 _(:з」∠)_

因为每一次只能交换一个$2^k$的块,并且$2$的不同次幂之间不会相互影响
话一句话来说,考虑交换长度为$2^k$的块时,所有长度为$2^{k-1}$的块的顺序必须已经排好
且长度为$2^k$的块,只能有至多两块位置不对
于是我们搞一发$DFS$就好了,时间复杂度:$O(n \log n)$

【BZOJ 3917】[Baltic2014] sequence

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3917
神犇题解Ⅰ:http://blog.csdn.net/lcrtest/article/details/51312981
神犇题解Ⅱ:http://blog.csdn.net/neither_nor/article/details/52604754

吐槽

他们说这题是APIO 2016练习赛的题目,为什么我一点印象都没有 QwQ
想了很久都只会$O(\frac{n^2}{64})$的暴力,我也很绝望啊…..

解题报告

我们发现,对于比较高的位数来讲,其一样的数在一起
考虑将一样的数合在一起,并且从低位到高位处理

记录二进制状态$f_{i,j}$表示在第$i$位的时候,第$j$块里需要哪些数
如果当前只需要一个数了,那么就可以直接返回辣!(如果是0需要特判)
否则的话,我们枚举这一位在第一个数中是多少
因为下一层中连续的区间长度大概都比现在这一位连续的区间长10倍
所以我们可以把这一位中的状态每十个合成一块,下一层的话又是一个递归子问题,我们可以递归下去
考虑每一层的总复杂度:第$i$层有$10^i$个分叉,每个分叉内有$\frac{n}{10^i}$个块,于是每一层的复杂度是$O(n)$的
下面我们来总复杂度$T(n)=10 \cdot T(\frac{n}{10}) + n$
根据主定理,这货是$O(n \log{n})$的

【BZOJ 4294】[PA2015] Fibonacci

相关链接

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

解题报告

做这题,我们需要有一个前置结论:

Fibonacci数列在$\bmod 10^n$的时候,循环节为$6 \times 10^n$

至于这个结论怎么证明,我也不知道
不过这个结论可以用这里的知识自己搞出来:传送门

那么知道了这个结论之后
我们就可以从低位到高位DFS了
每一层只会尝试$0 \sim 9$,虽然看起来会$T$
不过复杂度是玄学,所以跑得飞快

【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 1024】[SCOI2009] 生日快乐

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

算一算发现状态只有五六百种的样子
再加上每个状态的转移只有不超过10个
于是就可以记忆话搜索辣!
然而似乎直接暴搜也可以过 (╯‵□′)╯︵┻━┻

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)<0?-(x):(x))
using namespace std;

const double INF = 1e9;
const double EPS = 1e-3;

struct Data{
	double x,y,val;
	inline Data() {}
	inline Data(double x, double y, double val):x(x),y(y),val(val) {
		if (x < y) swap(x, y);
	}
	inline bool operator < (const Data &tmp) const {
		if (abs(tmp.x - x) < EPS && abs(tmp.y - y) < EPS) return 0;
		else if (tmp.x - x > EPS) return 1;
		else if (x - tmp.x > EPS) return 0;
		else if (tmp.y - y > EPS) return 1;
		else return 0;  
	}
};
set<Data> S;
set<Data>::iterator itr;

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

double DFS(double x, double y, int n) {
	if (n == 1) {
		if (x < y) swap(x, y);
		return x / y; 
	} else {
		itr = S.find(Data(x,y,0));
		if (itr != S.end()) return itr->val;
		else {
			double ret = INF;
			for (int i=1;i*2<=n;i++) {
				ret = min(ret, max(DFS(x*i/n,y,i), DFS(x*(n-i)/n,y,n-i)));
				ret = min(ret, max(DFS(x,y*i/n,i), DFS(x,y*(n-i)/n,n-i)));
			}
			S.insert(Data(x,y,ret));
			return ret;
		}
	}
}

int main(){
	int x=read(),y=read(),n=read();
	printf("%.6lf\n",DFS(x,y,n));
	return 0;
}

【UVa 11464】Even Parity

题目传送门:https://uva.onlinejudge.org/index.php&problem=2459
中文题面:《算法竞赛·入门经典·训练指南》P15

瞄一眼,觉得是这道题:http://www.lydsy.com/JudgeOnline/problem.php?id=3503
结果仔细一看:这题居然不能用线性基来搞,因为没法保证改变的数最少QAQ

还是是能用std的做法:
枚举第一行的所有状态,之后递推出整个棋盘的局面
然后计算更改量,最后用更改量来更新答案
复杂度:\(O({2^n} \cdot {n^2})\)