---恢复内容开始---
1、
http://www.spoj.com/problems/KAOS/
题意：给定n个字符串，统计字符串(s1, s2)的对数，使得s1的字典序比s2的字典序要大，s1反一反（abc->cba，记为s1’）比s2’的字典序要小。
做法：先把字符串排序，当我们把s[i]当成题意中的s1的时候,j > i,s[j]是不用管的,那我们只需要用Trie树按序插入s',然后统计答案。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <time.h>
#include <string>
#include <stack>
#include <set>
#include <map>
#include <iostream>
#include <bitset>
#include <algorithm>
using namespace std;
#define MP make_pair
#define PB push_back
typedef long long LL;
typedef pair<int, int> Pii;
const int inf = 0x3f3f3f3f;
const LL INF = (1uLL << ) - ;
const LL mod = ;
const int N = + ;
const double Pi = acos(-1.0);
const int maxn = 1e5 + ;
int trie[maxn << ][];
int cnt[maxn << ];
int tol = ;
struct node{
char s[];
bool operator < (const node & a)const{
return strcmp(a.s,s) > ;
}
}S[maxn];
int sum(int x) {
int len = strlen(S[x].s);
int now = ;
int res = ;
for(int i = len - ; i >= ; i--) {
int id = S[x].s[i] - 'a';
for(int j = id + ; j < ; j++) {
res += cnt[trie[now][j]];
}
now = trie[now][id];
}
for(int i = ; i < ; i++)res += cnt[trie[now][i]];
return res;
}
int is(int x) {
int len = strlen(S[x].s);
int now = ;
for(int i = len - ; i >= ; i--) {
int id = S[x].s[i] - 'a';
if(!trie[now][id]) {
trie[now][id] = ++tol;
}
now = trie[now][id];
++cnt[now];
}
return sum(x);
} int main() {
#ifdef local
freopen("in", "r", stdin);
// freopen("w","w",stdout);
#endif
// ios::sync_with_stdio(false);
// cin.tie(0);
int n;
LL ans = ;
scanf("%d",&n);
for(int i = ; i < n; i++)scanf("%s",S[i].s);
sort(S,S+n);
for(int i = ; i < n; i++) {
ans = ans + is(i);
}
printf("%lld\n",ans);
}
KAOS
2、
http://www.spoj.com/problems/STARSBC/
题意：一个圆上有n个等分点，现在从一个点出发，指定k，不停地隔k个点连边（样例请看link），问有多少种不同的方法，使得所有的点都被连起来。两种情况是一样的，当且仅当他们旋转若干角度以后是一样的。
做法：要能把所有点连起来那么gcd(k,n)肯定等于1,因为要把所有点连起来也就表示 k * x % n 能得到0 - n - 1所有值,一开始x为0时，k * x % n = 0,如果找到一个y使得k * y % n = 0,那就会陷入一个循环了，如果gcd(k,n)等于c，那k * n / c % n是等于0的，也就是说当点移动了n / c次后它就会陷入循环，很明显c取1的时候才能走完所有点，那这题就是要求出gcd(x,n)==1,且x < n的所有x，但是要去掉重复的，什么时候两个情况会一样呢。假如两个k分别取x , y，当x + y等于n的时候这两种情况就会一样了，这个画图看一下就行了，证明略，gcd(x,n) == gcd(n - x, n)这个结论也好推，所以当gcd(x,n)等于1那gcd(n - x,n)也等于1，那答案就等于欧拉(n) / 2.
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <time.h>
#include <string>
#include <stack>
#include <set>
#include <map>
#include <iostream>
#include <bitset>
#include <algorithm>
using namespace std;
#define MP make_pair
#define PB push_back
typedef long long LL;
typedef pair<int, int> Pii;
const int inf = 0x3f3f3f3f;
const LL INF = (1uLL << ) - ;
const LL mod = ;
const int N = + ;
const double Pi = acos(-1.0);
const int maxn = 1e5 + ;
int prime[maxn];
bool vis[maxn];
int tol;
void init() {
for(int i = ; i < maxn; i++) {
if(!vis[i])prime[tol++] = i;
for(int j = ; j < tol && i * prime[j] < maxn; j++){
vis[i * prime[j]] = ;
if(i % prime[j] == )break;
}
}
}
int main() {
#ifdef local
freopen("in", "r", stdin);
// freopen("w","w",stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
init();
int n;
while(~scanf("%d", &n)) {
int ans = n;
int cnt = ;
while(cnt < tol && prime[cnt] * prime[cnt] <= n) {
if(n % prime[cnt] == ) {
ans -= ans / prime[cnt];
while(n % prime[cnt] == )n /= prime[cnt];
}
cnt++;
}
if(n > ) {
ans -= ans / n;
}
ans >>= ;
printf("%d\n", ans);
}
}
STARSBC
3、
http://www.spoj.com/problems/ODDDIV/
题意：给出一个正奇数K，两个正整数low，high。有多少整数属于[low, high]，且包含K个因子。
做法：K是正奇数，表示n = p1 ^ m1 * p2 ^ m2 * ... * pk^mk,约数个数是(m1+1)*(m2+1)*...*(mk+1)那m肯定是偶数，所以我们可以bfs拓展一下，把k所有情况都跑出来，这样的数不会很多，数量在1e6左右，跑出来之后排序，二分结果就行了
//题解出了。自己弱智了点，因为m的数量是偶数，那这些数肯定是平方数，所以直接枚举2 - 1e5的平方来预处理就可以了，不用写这样麻烦的拓展
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <time.h>
#include <string>
#include <stack>
#include <set>
#include <map>
#include <iostream>
#include <bitset>
#include <algorithm>
using namespace std;
#define MP make_pair
#define PB push_back
typedef long long LL;
typedef pair<int, int> Pii;
const int inf = 0x3f3f3f3f;
const LL INF = (1uLL << ) - ;
const LL mod = ;
const int N = + ;
const double Pi = acos(-1.0);
const int maxn = 1e5 + ;
int prime[maxn];
bool vis[maxn];
int tol;
void init() {
for(int i = ; i < maxn; i++) {
if(!vis[i])prime[tol++] = i;
for(int j = ; j < tol && i * prime[j] < maxn; j++) {
vis[i * prime[j]] = ;
if(i % prime[j] == )break;
}
}
}
vector<LL>A[maxn];
struct node {
int h;
LL Num;
int _k;
};
queue<node>Q;
void bfs() {
node start = (node) {
-, ,
};
A[].PB();
Q.push(start);
while(!Q.empty()) {
node now = Q.front();
Q.pop();
for(int i = now.h + ; i < tol; i++) {
LL p = prime[i];
LL F = p * p;
LL die = ;
int num;
for(num = ; ; num += ) {
die *= F;
if(die <= 10000000000LL / now.Num && now._k * (num + ) <= ) {
A[now._k * (num + )].PB(now.Num * die);
Q.push((node) {
i, now.Num * die, now._k * (num + )
});
} else break;
}
if(num == )break;
}
}
}
bool vi[maxn];
int k;
int bs(LL x) {
int l = , r = A[k].size();
while(l + < r) {
int mid = (l + r) >> ;
if(A[k][mid] <= x) {
l = mid;
} else r = mid;
}
while(l >= && A[k][l] > x) {
l--;
}
return l;
}
int main() {
#ifdef local
freopen("in", "r", stdin);
// freopen("w","w",stdout);
#endif
ios::sync_with_stdio(false);
cin.tie();
init();
bfs();
int T;
cin >> T;
while(T--) {
LL l, r;
cin >> k >> l >> r;
if(!vi[k]) {
sort(A[k].begin(), A[k].end());
vi[k] = ;
}
cout<< upper_bound(A[k].begin(), A[k].end(), r) -upper_bound(A[k].begin(), A[k].end(), l - )<<endl;;
}
}
ODDDIV
4、
http://codeforces.com/contest/287/problem/D
题意：
定义排列p = p1, p2, ..., pn。
定义函数f(p, k)用来转换p排列，k是转换参数, k > 1。
假设排列p的长度为n，首先把p按长度k进行分块，若最后一块长度不足k，则其长度为n%k，然后分别对每一块循环左移一位，得到一个新的排列。
给定n，请输出 f(f(...f(p = [1,2,...,n],2)...,n-1,),n)的结果。
n <= 1e6
做法：
把f(p,k)右移一位，发现这个序列就是原本序列p的一个子序列（下标modk==1的数组成的）右移一位得到，所以我们把p的那个子序列先右移，再把整个序列左移就相当于进行了一次操作，每次的复杂度是n/k + 1,n / 2 + n / 3 + ... n / n 这样的复杂度是nlogn.用数组模拟一下
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <time.h>
#include <string>
#include <stack>
#include <set>
#include <map>
#include <iostream>
#include <bitset>
#include <algorithm>
using namespace std;
#define MP make_pair
#define PB push_back
typedef long long LL;
typedef pair<int, int> Pii;
const int inf = 0x3f3f3f3f;
const LL INF = (1uLL << ) - ;
const LL mod = ;
const int N = + ;
const double Pi = acos(-1.0);
const int maxn = 1e6 + ;
int Q[maxn << ];
char ch[];
int num;
inline void out(int x){
num = ;
while(x)ch[++num] = x % , x /= ;
while(num)putchar(ch[num--] + );
}
int main() {
#ifdef local
freopen("in", "r", stdin);
// freopen("w","w",stdout);
#endif
// ios::sync_with_stdio(false);
// cin.tie(0);
int n;
cin>>n;
for(int i = ; i <= n; i++)Q[i] = i;
for(int i = ; i <= n; i++){
int x = ;
for(int j = i - ; j < n + i - ; j += i){
swap(x,Q[j]);
}
Q[n + i - ] = x;
}
for(int i = n; i < n << ; i++){
out(Q[i]);
putchar(' ');
}
}
Shifting
5、
http://codeforces.com/contest/21/problem/D
题意：
给出一个无向带权图，问从1号点出发，通过所有的边至少一次，再回到1号点，需要花费的最少代价是多少。存在自环和重边。
如果无法满足上述要求，那么输出-1。
节点数n，边数m。(1 <= n <= 15, 0 <= m <= 2000)
每条边包含3个属性u, v, w, u和v是边的端点，w是通过边的代价。(1 <= x,y <= n, 1 <= w <= 1e4)。
做法：
从一个点出发走完全部边然后回到原点，这个就是欧拉回路，欧拉回路的条件是全部度数都是偶数，如果有不为偶数度数的点，我们可以把这些点互相连起来，使得这些点都变成偶数点，这是一定可行的，因为奇数度数的点必定有偶数个，这个操作我们可以用dfs也可以用状压dp来搞。连起来的时候的边权就是这两点之间的最短距离，这个最短距离我们可以通过Floyd预处理来弄。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <time.h>
#include <string>
#include <stack>
#include <set>
#include <map>
#include <iostream>
#include <bitset>
#include <algorithm>
using namespace std;
#define MP make_pair
#define PB push_back
typedef long long LL;
typedef pair<int, int> Pii;
const int inf = 0x3f3f3f3f;
const LL INF = (1uLL << ) - ;
const LL mod = ;
const int N = + ;
const double Pi = acos(-1.0);
const int maxn = 1e6 + ;
int E[][];
int d[];
int sum = ;
bool vis[];
int cnt = ;
int num[];
int dfs(int cur) {
if(cur == cnt)return ;
if(vis[cur]) {
return dfs(cur + );
}
vis[cur] = ;
int res = inf;
for(int i = ; i < cnt; i++) {
if(!vis[i]) {
vis[i] = ;
res = min(res , E[num[cur]][num[i]] + dfs(cur + ));
vis[i] = ;
}
}
vis[cur] = ;
return res;
}
int dp[<<];
int main() {
#ifdef local
freopen("in", "r", stdin);
// freopen("w","w",stdout);
#endif
ios::sync_with_stdio(false);
cin.tie();
memset(E, 0x3f, sizeof E);
int n, m;
cin >> n >> m;
for(int i = ; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
sum += w;
E[u][v] = E[v][u] = min(E[u][v], w);
d[u]++, d[v]++;
}
for(int k = ; k <= n; k++) {
for(int i = ; i <= n; i++) {
for(int j = ; j <= n; j++) {
E[i][j] = min(E[i][j], E[i][k] + E[k][j]);
}
}
}
if(m == ) {
cout << << endl;
return ;
}
for(int i = ; i <= n; i++) {
if(E[][i] == E[][] && d[i]) {
cout << - << endl;
return ;
}
}
int sta = ;
for(int i = ; i <= n; i++) {
if(d[i] % == ) sta += ( << (i - ));
}
memset(dp,0x3f,sizeof dp);
dp[sta] = ;
for(int i = ; i < ( << n); i++) {
if((i & sta) == sta) {
for(int j = ; j < n; j++) {
if(! ((i >> j) & ))
for(int z = j + ; z < n; z++) {
if(!((i >> z) & )){
dp[i|(<<j)|(<<z)] = min(dp[i|(<<j)|(<<z)],dp[i] + E[j + ][z + ]);
}
}
}
}
}
cout<<dp[( << n) - ] + sum<<endl;
}
状压
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <time.h>
#include <string>
#include <stack>
#include <set>
#include <map>
#include <iostream>
#include <bitset>
#include <algorithm>
using namespace std;
#define MP make_pair
#define PB push_back
typedef long long LL;
typedef pair<int, int> Pii;
const int inf = 0x3f3f3f3f;
const LL INF = (1uLL << ) - ;
const LL mod = ;
const int N = + ;
const double Pi = acos(-1.0);
const int maxn = 1e6 + ;
int E[][];
int d[];
int sum = ;
bool vis[];
int cnt = ;
int num[];
int dfs(int cur) {
if(cur == cnt)return ;
if(vis[cur]){
return dfs(cur + );
}
vis[cur] = ;
int res = inf;
for(int i = ; i < cnt; i++) {
if(!vis[i]){
vis[i] = ;
res = min(res , E[num[cur]][num[i]] + dfs(cur + ));
vis[i] = ;
}
}
vis[cur] = ;
return res;
}
int main() {
#ifdef local
freopen("in", "r", stdin);
// freopen("w","w",stdout);
#endif
ios::sync_with_stdio(false);
cin.tie();
memset(E, 0x3f, sizeof E);
int n, m;
cin >> n >> m;
for(int i = ; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
sum += w;
E[u][v] = E[v][u] = min(E[u][v], w);
d[u]++, d[v]++;
}
for(int k = ; k <= n; k++) {
for(int i = ; i <= n; i++) {
for(int j = ; j <= n; j++) {
E[i][j] = min(E[i][j], E[i][k] + E[k][j]);
}
}
}
if(m == ){
cout<<<<endl;
return ;
}
for(int i = ; i <= n; i++) {
if(E[][i] == E[][] && d[i]) {
cout << - << endl;
return ;
}
}
for(int i = ; i <= n; i++) {
if(d[i] & )num[cnt++] = i;
}
cout << sum + dfs() << endl;
}
dfs
6、
http://codeforces.com/problemset/problem/732/D
题意：
你需要在n天内通过m门课程，课程下标1 - m，每天可以考完一科科目，或者准备一些科目，或者休息。
第i天可以考的科目为di, di=0表示这天不能考试，复习第i门课需要花费的时间为ai。
问复习完所有课程需要花费的最小天数是多少天，如果复习不完，输出-1。
(1 <= n, m <= 1e5), (0 <= di <= m)，(1 <= ai <= 1e5)。
做法：
这种题一般都是二分答案，二分答案，判断里面考试的日期全部贪心倒着选后面的时间，选够m个，然后模拟判断。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <time.h>
#include <string>
#include <stack>
#include <set>
#include <map>
#include <iostream>
#include <bitset>
#include <algorithm>
using namespace std;
#define MP make_pair
#define PB push_back
typedef long long LL;
typedef pair<int, int> Pii;
const int inf = 0x3f3f3f3f;
const LL INF = (1uLL << ) - ;
const LL mod = ;
const int N = + ;
const double Pi = acos(-1.0);
const int maxn = 1e6 + ;
int d[maxn];
Pii F[maxn];
bool vis[maxn];
int n , m;
int a[maxn];
bool judge(int x){
memset(vis,,sizeof vis);
int cnt = ;
for(int i = x; i >= ;i--){
if(d[i] != && !vis[d[i]]){
vis[d[i]] = ;
F[cnt++] = MP(d[i],i);
}
}
if(cnt < m)return ;
else {
int sum = ;
int now = ;
while(cnt--){
sum += F[cnt].second - now - ;
if(sum < a[F[cnt].first])return ;
else sum -= a[F[cnt].first];
now = F[cnt].second;
}
return ;
}
}
int main() {
#ifdef local
freopen("in", "r", stdin);
// freopen("w","w",stdout);
#endif
ios::sync_with_stdio(false);
cin.tie();
cin >> n >> m;
for(int i = ; i <= n; i++)cin>>d[i];
for(int i = ; i <= m; i++)cin>>a[i];
int l = ,r = n + ;
int ans = -;
while(l + < r){
int mid = (l + r) >> ;
if(judge(mid)){
r = mid;
ans = r;
}
else l = mid;
}
cout<<ans<<endl;
}
Exams
7、
http://codeforces.com/problemset/problem/396/B
题意：
定义v(n)是不超过n的最大素数, u(n)是大于n的最小素数。
以分数形式"p/q"输出 sigma(i = 2 to n) (1 / (v(i)*u(i))), pq为互质整数且q > 0。
t，测试样例数。
每个样例输入包含一个n。(2 <= n <= 1e9)。
做法：
直接列出来看下有什么规律假如n够大
1/(2 * 3) + 1/(3*5) +1/(3*5)+1/(5*7)+1/(5*7)+...+{1/(v(n) * u(n))+..+1/(v(n) * u(n)),一共有n - v(n) + 1个}
我们知道(a-b)/(a*b) = 1/a - 1/b.所以上面的式子可以化简成
1/2 - 1/v(n) + (n - v(n) + 1)/(v(n) * u(n))
v(n)和u(n)都可以直接暴力找，因为1e9以内的素数间隔不是很大
所以最后再通分一下就可以了
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <time.h>
#include <string>
#include <stack>
#include <set>
#include <map>
#include <iostream>
#include <bitset>
#include <algorithm>
using namespace std;
#define MP make_pair
#define PB push_back
typedef long long LL;
typedef pair<int, int> Pii;
const int inf = 0x3f3f3f3f;
const LL INF = (1uLL << ) - ;
const LL mod = ;
const int N = + ;
const double Pi = acos(-1.0);
const int maxn = 1e6 + ;
int n;
bool judge(int x) {
int k = sqrt(x);
for(int i = ; i <= k; i++) {
if(x % i == )return ;
}
return ;
}
int d() {
for(int i = n;; i--) {
if(judge(i))return i;
}
}
int h() {
for(int i = n + ;; i++) {
if(judge(i))return i;
}
}
LL gcd(LL a, LL b) {
return b ? gcd(b, a % b) : a;
}
int main() {
#ifdef local
freopen("in", "r", stdin);
// freopen("w","w",stdout);
#endif
ios::sync_with_stdio(false);
cin.tie();
int cas = ;
cin >> cas;
while(cas--) {
cin >> n;
int v = d();
int u = h();
LL s = 2LL * u * v;
LL t = s / - * u + * n - * v + ;
cout << t / gcd(s, t) << "/" << s / gcd(s, t) << endl;
}
}
On Sum of Fractions
8、
http://www.spoj.com/problems/FACVSPOW/
题意:
输入a，找到满足n!>a^n 最小的n。
数据
第一行T(1 <= T <= 1e5)，表示测试样例数.(2 <= a <= 1e6)。
做法：应该算简单题了。n!和a^n都很大，所以我们应该适当转化一下，两边log一下式子就变成了log(n!) > nlog(a).左边就相当于求和(log(i),0 < i <= n)，预处理这样一个前缀和，然后直接二分n就可以了
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <time.h>
#include <string>
#include <stack>
#include <set>
#include <map>
#include <iostream>
#include <bitset>
#include <algorithm>
using namespace std;
#define MP make_pair
#define PB push_back
typedef long long LL;
typedef pair<int, int> Pii;
const int inf = 0x3f3f3f3f;
const LL INF = (1uLL << ) - ;
const LL mod = ;
const int N = + ;
const double Pi = acos(-1.0);
const int maxn = 3e6 + ;
double ans[maxn];
int main() {
#ifdef local
freopen("in", "r", stdin);
// freopen("w","w",stdout);
#endif
ios::sync_with_stdio(false);
cin.tie();
ans[] = ;
for(int i = ; i < maxn; i++){
ans[i] = ans[i-] + log(i);
}
int t;
cin>>t;
while(t--){
int a;
cin>>a;
int l = ,r = maxn;
double c = log(a);
while(l + < r){
int mid = l + r >> ;
if(ans[mid] >= mid * c){
r = mid;
}
else l = mid;
}
cout<<r<<endl;
}
}
FACVSPOW