Codeforces Round #261 (Div. 2)

题目链接

A：给定两点找正方形其他两点。
分在一条线和对角线的情况判断即可

B：一个序列选出最大和最小的数字，问差值很有几种选法。
有不同数字的情况就是两数个数相乘，只有一个数字就是C2n

C：n个学生，k辆车，d天，要求学生两两之间不能在同一辆车一起d天，问怎么一个安排的方案
对于每个学生而言，在d天的坐车情况，只要不和其他人重复即可，这样进行dfs构造序列，如果能构造出n个不同序列，就是可以的，如果不能就输出-1

D：求f(1, i, ai) > f(j, n, aj)的个数
用树状数组，就可以搞了，类似求逆序数那样先把数字离散化掉，然后从前往后搞一次，记录下来，再从后往前搞一次即可

E：一个有向图，找出一条最长路径，满足路上的长度是一直递增的
dp，dp[i]表示i结点的情况，然后先把边按权值排序，这样的话就保证从小到大，这样遍历到每条边，对于当前边而言它都是最大边，肯定可以加进去，然后进行dp即可，注意对于一个权值的边可能有多条，这样的话如果直接状态转移，就转移到当前长度相同的边，其实这里只需要再多开一个数组记录下来，每次状态转移就在这个数组基础上状态转移，转移完在赋值过去即可

代码：

A:

#include <cstdio>
#include <cstring>
#include <cstdlib>
int x1, y1, x2, y2;

bool judge() {
    if (y1 == y2) {
    int len = abs(x2 - x1);
    printf("%d %d %d %d\n", x1, y1 + len, x2, y2 + len);
    }
    else if (x1 == x2) {
    int len = abs(y1 - y2);
    printf("%d %d %d %d\n", x1 + len, y1, x2 + len, y2);
    }
    else {
    if (abs(x1 - x2) != abs(y1 - y2)) return false;
    printf("%d %d %d %d\n", x1, y2, x2, y1);
    }
    return true;
}

int main() {
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    if (!judge()) printf("-1\n");
    
    return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 200005;

int n, b[N], Max = 0, Min = INF;

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
    scanf("%d", &b[i]);
    Max = max(Max, b[i]);
    Min = min(Min, b[i]);
    }
    int cnt1 = 0, cnt2 = 0;
    for (int i = 0; i < n; i++) {
    if (Max == b[i])
        cnt1++;
    if (Min == b[i])
        cnt2++;
    }
    if (Max == Min) printf("0 %lld\n", (long long)cnt1 * (cnt1 - 1) / 2);
    else printf("%d %lld\n", Max - Min, (long long)cnt1 * cnt2);
    return 0;
}

#include <cstdio>
#include <cstring>

const int N = 1005;

int n, k, d, sum = 0, ans[N][N], save[N];

bool dfs(int u) {
	int i;
	if (u == d) {
		for (i = 0; i < d; i++)
			ans[sum][i] = save[i];
		sum++;
		if (sum == n) {
			for (i = 0; i < d; i++) {
				for (int j = 0; j < n - 1; j++)
					printf("%d ", ans[j][i]);
				printf("%d\n", ans[n - 1][i]);	
			}
			return true;
		}
		return false;
	}
	for (i = 1; i <= k; i++) {
		save[u] = i;
		if (dfs(u + 1)) return true;
	}
	return false;
}

int main() {
	scanf("%d%d%d", &n, &k, &d);
	if (!dfs(0)) printf("-1\n");
	return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int lowbit(int x) {
    return (x&(-x));
}

const int N = 1000005;
int n, bit[N], bit2[N], save[N], bit3[N];
struct Num {
    int a, b, id;
} nu[N];

void add(int *bit, int x, int v) {
    while (x < N) {
        bit[x] += v;
        x += lowbit(x); 
    }
}

int get(int *bit, int x) {
    int ans = 0;
    while (x) {
        ans += bit[x];
        x -= lowbit(x);
    }
    return ans;
}

bool cmp1(Num a, Num b) {
return a.a < b.a;
}

bool cmp2(Num a, Num b) {
return a.id < b.id;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &nu[i].a);
        nu[i].id = i;   
    }
    sort(nu, nu + n, cmp1);
    int cnt = 1;
    nu[0].b = 1;
    for (int i = 1; i < n; i++) {
        if (nu[i].a != nu[i - 1].a)
            cnt++;
        nu[i].b = cnt;
    }
    sort(nu, nu + n, cmp2);
    for (int i = 0; i < n; i++) {
        add(bit, nu[i].b, 1);
        add(bit2, get(bit, nu[i].b) - get(bit, nu[i].b - 1), 1);
    }
    long long ans = 0;
    for (int i = n - 1; i >= 0; i--) {
        add(bit2, get(bit, nu[i].b) - get(bit, nu[i].b - 1), -1);
        add(bit, nu[i].b, -1);
        add(bit3, nu[i].b, 1);
        int tmp = get(bit3, nu[i].b) - get(bit3, nu[i].b - 1);
        ans += get(bit2, n) - get(bit2, tmp);
        
    }
    printf("%lld\n", ans);
    //system("pause");
    return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 300005;

int n, m, dp[2][N];

struct Edge {
    int u, v, w;
} e[N];

bool cmp(Edge a, Edge b) {
    return a.w < b.w;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++)
        scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
    sort(e, e + m, cmp);
    for (int i = 0; i < m; i++) {
        int j;
        for (j = i; e[i].w == e[j].w; j++)
            dp[1][e[j].v] = max(dp[1][e[j].v], dp[0][e[j].u] + 1);
        for (j = i; e[i].w == e[j].w; j++)
            dp[0][e[j].v] = dp[1][e[j].v];
        i = j - 1;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, dp[0][i]);
    printf("%d\n", ans);
    //system("pause");
    return 0;
}