比赛链接：http://codeforces.com/contest/702
A题求连续最长上升自序列。
[暴力题] for一遍，前后比较就行了。
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair <int, int> P;
const int N = 1e5 + ;
int a[N]; int main()
{
int n;
scanf("%d" , &n);
int temp = , res = ;
scanf("%d" , a + );
for(int i = ; i <= n ; ++i) {
scanf("%d" , a + i);
if(a[i] > a[i - ]) {
temp++;
res = max(res, temp);
}
else {
temp = ;
}
}
printf("%d\n" , res);
return ;
}
B题求有多少对数的和等于2的幂（即a[i] + a[j] = 2的幂）。
[map乱搞] 先用map存a[i]出现的次数。因为2的幂的个数也就30多个，那我们可以for一遍a数组，然后枚举2的幂。
统计mp[2的幂 - a[i]]的大小。要是2的幂-a[i]等于a[i]，统计的时候减一就好了。
最后答案除以2，因为每对重复统计了两次。
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
typedef __int64 LL;
typedef pair <int, int> P;
const int N = 1e5 + ;
map <LL , LL> mp;
LL num[];
LL a[N]; int main()
{
mp.clear();
num[] = ;
for(int i = ; i <= ; ++i) {
num[i] = num[i - ] * ;
}
int n;
scanf("%d" , &n);
for(int i = ; i <= n ; ++i) {
scanf("%lld" , a + i);
mp[a[i]]++;
}
LL res = ;
for(int i = ; i <= n ; ++i) {
for(int j = ; j <= ; j++) {
if(num[j] < a[i])
continue;
res += mp[num[j] - a[i]];
if(num[j] == * a[i])
res--;
}
}
printf("%lld\n" , res / );
return ;
}
C题题意是给你n个城市和m个塔的坐标，问你塔的信号半径最少是多少能够覆盖所有的城市。
[二分答案] 二分半径，每次二分一下 然后判断半径的可行性，可行性的话for一遍就好了。
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
typedef __int64 LL;
typedef pair <int, int> P;
const int N = 1e5 + ;
LL a[N] , b[N];
int n , m; bool check(LL r) {
int index = , cnt = ;
for(int i = ; i <= n , index <= m; ++i) {
if(a[i] >= b[index] - r && a[i] <= b[index] + r) {
cnt++;
continue;
}
else {
index++;
i--;
}
}
if(cnt >= n)
return true;
return false;
} int main()
{
scanf("%d %d", &n , &m);
for(int i = ; i <= n ; ++i) {
scanf("%lld" , a + i);
}
for(int i = ; i <= m ; ++i) {
scanf("%lld" , b + i);
}
LL l = , r = *1e9+;
while(l < r) {
LL mid = (l + r) / ;
if(check(mid)) {
r = mid;
}
else {
l = mid + ;
}
}
printf("%lld\n" , r);
return ;
}
D题条件是：d代表路程长度，k代表车子每行驶k长度就会坏，a代表车行驶单位长度的时间，b代表人走路单位长度的时间，t代表坏的车修好时间。
车好像一开始没坏，问你最少需要多少时间能到终点。
[分类讨论] 一开始肯定要开车。后来我是比较车的平均速度(k/(k*a+t))和人的平均速度(1/b)。
要是人的速度大于等于车的速度，那走路到终点就好了。
不然的话就开车，但是开车开了k的整数倍，剩下路程(d')要是不到k的话，那讨论剩下的路 人和车谁话的时间最少(min(d'*a+k, d'*b))。
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
typedef __int64 LL;
typedef pair <int, int> P;
const int N = 1e5 + ; int main()
{
LL d , k , a , b , t , res = ;
cin >> d >> k >> a >> b >> t;
LL ans = d;
d -= k;
res = k*a;
if(d <= ) { //一开始k < d的情况
cout << a * ans << endl;
return ;
}
double car = k*1.0 / (a*k + t) , peo = 1.0 / b; //车和人的速度
if(peo >= car) { //人的速度大于等于车的速度
res += d * b;
cout << res << endl;
return ;
}
LL temp = d;
d -= d / k * k; //车后来开了k的整数倍
res += temp / k * (k*a + t);
if(d > ) { //剩下的路 车和人 取最小的时间
LL temp1 = t + d * a , temp2 = d * b;
res += min(temp1 , temp2);
}
cout << res << endl;
return ;
}
E. Analysis of Pathes in Functional Graph
E题题意是有n个点(编号0 ~ n - 1)，n条单向边，i和a[i]相连并指向a[i]，然后给你每条边的权值。
问你从每个点出发，走k条边，走的路径权值和是多少，还有求其中最小的边是多少。
[倍增法] n条边 所以成环，单向 所以每条路径是唯一的。 可以想象成每个数开头之后的都是循环下去的数组。
可以用倍增法 类似RMQ的做法解，先预处理一下，par[i][j]表示从i点开始2^i后的点的编号，sum[i][j]表示i点开始2^j条边的路径权值和，min[i][j]表示i点开始2^j条边中最小的边权。
查询的时候利用k的二进制性质就行了，也是倍增。
//#pragma comment(linker, "/STACK:102400000, 102400000")
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
typedef __int64 LL;
typedef pair <int, int> P;
const int N = 1e5 + ;
int par[N][];
LL min_val[N][];
LL sum[N][]; void init(int n) {
for(int k = ; k < ; ++k) {
for(int i = ; i < n; ++i) {
par[i][k] = par[par[i][k - ]][k - ];
min_val[i][k] = min(min_val[i][k - ], min_val[par[i][k - ]][k - ]);
sum[i][k] = sum[i][k - ] + sum[par[i][k - ]][k - ];
}
}
} void solve(int root, LL x) {
LL res_min = 1e8 + , res_sum = ;
for(int k = ; k < ; ++k) {
if(x & (1LL << k)) {
res_sum += sum[root][k];
res_min = min(res_min, min_val[root][k]);
root = par[root][k];
}
}
printf("%lld %lld\n", res_sum, res_min);
} int main()
{
int n;
LL m;
scanf("%d %lld", &n, &m);
for(int i = ; i < n; ++i)
scanf("%d", &par[i][]);
for(int i = ; i < n; ++i) {
scanf("%lld", &min_val[i][]);
sum[i][] = min_val[i][];
}
init(n);
for(int i = ; i < n; ++i) {
solve(i, m);
}
return ;
}
F题不会