1 5 1 5 2 4 2 8 3 7 7 9
4
思路：贪心，先按左区间排，然后一直往后找就可以了，复杂度O(n);
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define max(a,b) ((a)>(b)?(a):(b))
const int N = 100005;
int t, n;
struct Seg {
int l, r;
}s[N];
void init() {
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d%d", &s[i].l, &s[i].r);
}
bool cmp(Seg a, Seg b) {
return a.l < b.l;
}
int solve() {
sort(s, s + n, cmp);
int ans = 0, rv = s[0].r;
for (int i = 1; i < n; i++) {
if (s[i].r > rv) {
ans = max(ans, rv - s[i].l);
rv = s[i].r;
}
else ans = max(ans, s[i].r - s[i].l);
}
return ans;
}
int main() {
scanf("%d", &t);
while (t--) {
init();
printf("%d\n", solve());
}
return 0;
}00:30 01:00 02:00 91:30 46:03 00:00
00:29 00:59 01:59 90:99 49:99
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INF 0x3f3f3f3f
char str[10];
int Sum(int *num) {
int sum = (num[0] * 10 + num[1]) * 60 + (num[2] * 10 + num[3]);
return sum;
}
struct Ans {
char str[5];
int num[4];
int nine;
int d;
}ans;
void solve() {
int num[4];
ans.nine = 0; ans.d = INF;
memset(ans.str, 0, sizeof(ans.str));
strcpy(ans.str, "9999");
num[0] = str[0] - ‘0‘; num[1] = str[1] - ‘0‘; num[2] = str[3] - ‘0‘; num[3] = str[4] - ‘0‘;
int sum = Sum(num);
for (num[0] = 0; num[0] < 10; num[0]++)
for (num[1] = 0; num[1] < 10; num[1]++)
for (num[2] = 0; num[2] < 10; num[2]++)
for (num[3] = 0; num[3] < 10; num[3]++) {
int s = Sum(num);
if (10 * abs(sum - s) >= sum) continue;
int dd = abs(sum - s);
int nine = 0;
for (int i = 0; i < 4; i++)
if (num[i] == 9) nine++;
if (nine >= ans.nine) {
if (nine == ans.nine) {
if (dd <= ans.d) {
if (dd == ans.d) {
char ss[5];
for (int k = 0; k < 4; k++)
ss[k] = num[k] + ‘0‘;
ss[4] = ‘\0‘;
if (strcmp(ss, ans.str) < 0) {
ans.nine = nine;
for (int j = 0; j < 4; j++) {
ans.num[j] = num[j];
ans.str[j] = num[j] + ‘0‘;
}
ans.d = dd;
}
}
else {
ans.nine = nine;
for (int j = 0; j < 4; j++) {
ans.num[j] = num[j];
ans.str[j] = num[j] + ‘0‘;
}
ans.d = dd;
}
}
}
else {
ans.nine = nine;
for (int j = 0; j < 4; j++) {
ans.num[j] = num[j];
ans.str[j] = num[j] + ‘0‘;
}
ans.d = dd;
}
}
}
printf("%d%d:%d%d\n", ans.num[0], ans.num[1], ans.num[2], ans.num[3]);
}
int main() {
while (gets(str) != NULL) {
if (str[0] == ‘0‘ && str[1] == ‘0‘ && str[3] == ‘0‘ && str[4] == ‘0‘) break;
solve();
}
return 0;
}1 10 1 20 123 456789
Case 1: 0 Case 2: 2 Case 3: 16
#include <stdio.h>
#include <string.h>
int x, y, ans, fuck;
int solve() {
ans = 0; fuck = 0;
for (int i = x; i * i * i <= y * 10 + 3; i++)
for (int j = i; i * i * i + j * j * j <= y * 10 + 3; j++) {
int sum = ((i * i * i + j * j * j) - 3);
if (sum % 10) continue; sum /= 10;
if (sum >=x && sum <= y) {
if (x == y) fuck++;
ans++;
}
}
return ans * 2 - fuck;
}
int main() {
int cas = 0;
while (~scanf("%d%d", &x, &y)) {
printf("Case %d: %d\n", ++cas, solve());
}
return 0;
}3 4 3 1 -5 2 2 -4 -1 5 3 -1 4 -4 -2
6 0 6
#include <stdio.h>
#include <string.h>
#include <queue>
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int N = 200005;
int t, n, num[N];
struct Node {
int sum, id;
}s[N];
void init() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &num[i]);
num[i + n] = num[i];
}
}
int solve() {
int ans = 0;
s[0].sum = 0; s[0].id = 0;
deque<Node>Q;
Q.push_front(s[0]);
for (int i = 1; i <= 2 * n; i++) {
s[i].sum = s[i - 1].sum + num[i];
s[i].id = i;
while (!Q.empty() && Q.back().sum >= s[i].sum) {Q.pop_back();}
while (!Q.empty() && s[i].id - Q.front().id > n) {Q.pop_front();}
Q.push_back(s[i]);
ans = max(ans, s[i].sum - Q.front().sum);
}
return ans;
}
int main() {
scanf("%d", &t);
while (t--) {
init();
printf("%d\n", solve());
}
return 0;
}4 3 3 1 -1 4 2 4 2 1 5
9
#include <stdio.h>
#include <string.h>
#include <vector>
#define max(a,b) ((a)>(b)?(a):(b))
#define INF 0x3f3f3f3f
using namespace std;
const int N = 50005;
int n, m, ans, dp[N][2];
struct Node {
int v, value;
Node(int vv, int va) {
v = vv; value = va;
}
};
vector<Node>g[N];
void init() {
int u, v, value;
ans = -INF;
memset(g, 0, sizeof(g));
for (int i = 0; i < m; i++) {
scanf("%d%d%d", &u, &v, &value);
ans = max(ans, value);
g[u].push_back(Node(v, value));
g[v].push_back(Node(u, value));
}
}
void dfs(int u, int fa) {
dp[u][0] = dp[u][1] = -INF;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i].v, value = g[u][i].value;
if (fa == v) continue;
dfs(v, u);
int t = 0;
if (dp[v][0] > 0) t = dp[v][0];
if (dp[u][0] < t + value) {
dp[u][1] = dp[u][0];
dp[u][0] = t + value;
}
else if (dp[u][1] < t + value)
dp[u][1] = t + value;
}
ans = max(ans, dp[u][0]);
ans = max(ans, dp[u][0] + dp[u][1]);
}
int main() {
while (~scanf("%d%d", &n, &m)) {
init();
dfs(1, 0);
printf("%d\n", ans);
}
return 0;
}3 3 2 1 1 2 3 3 1 1 2 3 0 0 0 0
2 1 6
#include <stdio.h>
#include <string.h>
const int N = 100005;
int t, n, sum, num[N];
void init() {
scanf("%d%d", &n, &sum);
for (int i = 0; i < n; i++)
scanf("%d", &num[i]);
}
int solve() {
int h = 0, r = 0, s = 0, ans = 0;
while (r < n) {
s += num[r];
if (s > sum) {
while (s > sum) {s -= num[h++];}
}
if (s == sum) {
int cal = 1;
for (int i = h; i < r; i++) {
if (num[i] == 0) cal++;
else break;
}
ans += cal;
}
r++;
}
return ans;
}
int main() {
scanf("%d", &t);
while (t--) {
init();
printf("%d\n", solve());
}
return 0;
}accmmmca
6
#include <stdio.h>
#include <string.h>
const int N = 2005;
const char s[4] = {"acm"};
char str[N];
long long dp[4][N];
long long DP() {
int len = strlen(str + 1);
for (int k = 0; k <= len; k++)
dp[0][k] = 1;
for (int i = 1; i <= 3; i++) {
dp[i][0] = 0;
for (int j = 1; j <= len; j++) {
if (str[j] == s[i - 1]) {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1];
}
else {
dp[i][j] = dp[i][j - 1];
}
}
}
return dp[3][len];
}
int main() {
while (gets(str + 1) != NULL) {
printf("%lld\n", DP());
}
return 0;
}6 2 1 2 0 0 -1 0 0 -2 0 0 1 0 0 2 1 4 0 0 -1 0 0 -2 0 0 1 0 0 2 1 4 0 0 -1 0 0 1 0 0 1 0 0 2 1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 1 1 0 0 0 1 0 0 3 1 -1 0 0 1 0 0 -2 0 0 1 0 0 4 0 0 -1 0 0
Case 1: 2 1 Case 2: 2 1 Case 3: 2 2 Case 4: 0 0 Case 5: 1 1 Case 6: 3 2
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
const int N = 100005;
struct Point {
double x, y, z;
double xk, yk, zk;
double s, e;
int vis;
} p[N];
int t, n, ansn, ansc;
double r;
void init() {
ansn = ansc = 0;
memset(p, 0, sizeof(p));
scanf("%d%lf", &n, &r);
for (int i = 0; i < n; i ++) {
scanf("%lf%lf%lf%lf%lf%lf", &p[i].x, &p[i].y, &p[i].z, &p[i].xk, &p[i].yk, &p[i].zk);
}
}
bool cmp(Point a, Point b) {
return a.e < b.e;
}
void solve() {
ansn = n;
for (int i = 0; i < n; i ++) {
double a = p[i].xk * p[i].xk + p[i].yk * p[i].yk + p[i].zk * p[i].zk;
double b = 2 * p[i].x * p[i].xk + 2 * p[i].y * p[i].yk + 2 * p[i].z * p[i].zk;
double c = p[i].x * p[i].x + p[i].y * p[i].y + p[i].z * p[i].z - r * r;
double dlt =b * b - 4 * a * c;
if (dlt < 0) {
ansn--;
continue;
}
double k1 = (-b + sqrt(dlt)) / (2 * a);
double k2 = (-b - sqrt(dlt)) / (2 * a);
if (k1 < 0 && k2 < 0) {
ansn--;
continue;
}
if (k2 < k1) {
if (k2 < 0) k2 = 0;
p[i].s = k2; p[i].e = k1;
}
else {
if (k1 < 0) k1 = 0;
p[i].s = k1; p[i].e = k2;
}
p[i].vis = 1;
}
sort(p, p + n, cmp);
double c = -1000000000;
for (int ii = 0; ii < n; ii ++) {
if (!p[ii].vis) continue;
if (p[ii].s > c) {
c = p[ii].e;
ansc ++;
}
}
}
int main() {
int cas = 0;
scanf("%d", &t);
while (t--) {
init();
solve();
printf("Case %d: %d %d\n", ++cas, ansn, ansc);
}
return 0;
}原文：http://blog.csdn.net/accelerator_/article/details/18404053