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