A
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = , MAXM = ;
//int to[MAXM << 1], nxt[MAXM << 1], Head[MAXN], ed = 1;
//int cost[MAXM << 1];
//inline void addedge(int u, int v, int c)
//{
// to[++ed] = v;
// nxt[ed] = Head[u];
// cost[ed] = c;
// Head[u] = ed;
//}
inline void read(ll &v)
{
v = ;
char c = ;
int p = ;
while (c < '' || c > '') {
if (c == '-') {
p = -;
}
c = getchar();
}
while (c >= '' && c <= '') {
v = (v << ) + (v << ) + c - '';
c = getchar();
}
v *= p;
}
int main()
{
ll T;
read(T);
while (T--) {
ll n, x, y, d;
read(n), read(x), read(y), read(d);
ll cha = abs(x - y);
if (cha % d == ) {
ll ans = cha / d;
printf("%I64d\n", ans);
continue;
} else {
ll anser = LLONG_MAX;
ll ans1, ans2;
ans1 = ans2 = LLONG_MAX;
if ((y - ) % d == ) {
ans1 = (x - ) / d;
if ((x - ) % d) {
ans1++;
}
ans1 += (y - ) / d;
}
if ((n - y) % d == ) {
ans2 = (n - x) / d;
if ((n - x) % d) {
ans2++;
}
ans2 += (n - y) / d;
}
anser = min(anser, min(ans1, ans2));
if (anser == LLONG_MAX) {
printf("-1\n");
} else {
printf("%I64d\n", anser);
}
}
}
}
B
注意一下坑点即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = , MAXM = ;
//int to[MAXM << 1], nxt[MAXM << 1], Head[MAXN], ed = 1;
//int cost[MAXM << 1];
//inline void addedge(int u, int v, int c)
//{
// to[++ed] = v;
// nxt[ed] = Head[u];
// cost[ed] = c;
// Head[u] = ed;
//}
inline void read(int &v)
{
v = ;
char c = ;
int p = ;
while (c < '' || c > '') {
if (c == '-') {
p = -;
}
c = getchar();
}
while (c >= '' && c <= '') {
v = (v << ) + (v << ) + c - '';
c = getchar();
}
v *= p;
}
vector<pair<int, char> > anss;
queue<pair<int, char> > que;
int main()
{
ios_base::sync_with_stdio();
cin.tie();
int n;
cin >> n;
string a;
cin >> a;
pair<int, char> cnt, zz;
cnt.first = cnt.second = ;
int sum = ;
for (int i = ; i <= n; i++) {
if (i == n) {
anss.push_back(cnt);
break;
}
if (a[i] != cnt.second) {
if (cnt.first != ) {
anss.push_back(cnt);
}
cnt.first = ;
cnt.second = a[i];
} else {
cnt.first++;
}
}
int sz = anss.size();
for (int i = ; i < sz; i++) {
if (anss[i].second == 'G') {
sum += anss[i].first;
}
}
int ans = ;
for (int i = ; i < sz; i++) {
cnt = anss[i];
if (cnt.second == 'G') {
if (cnt.first == sum) {
ans = max(ans, cnt.first);
} else {
ans = max(ans, cnt.first + );
}
} else {
if (cnt.first == ) {
if (i > && i < sz - ) {
ans = max(ans, anss[i - ].first + anss[i + ].first);
if (anss[i - ].first + anss[i + ].first != sum) {
ans = max(ans, anss[i - ].first + anss[i + ].first + );
}
}
}
}
}
cout << ans << endl;
}
C
sort一下算下贡献即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = , MAXM = ;
//int to[MAXM << 1], nxt[MAXM << 1], Head[MAXN], ed = 1;
//int cost[MAXM << 1];
//inline void addedge(int u, int v, int c)
//{
// to[++ed] = v;
// nxt[ed] = Head[u];
// cost[ed] = c;
// Head[u] = ed;
//}
inline void read(int &v)
{
v = ;
char c = ;
int p = ;
while (c < '' || c > '') {
if (c == '-') {
p = -;
}
c = getchar();
}
while (c >= '' && c <= '') {
v = (v << ) + (v << ) + c - '';
c = getchar();
}
v *= p;
}
int pre[];
vector<int> num[];
int main()
{
ios_base::sync_with_stdio();
cin.tie();
int n, m;
cin >> n >> m;
int u, v;
for (int i = ; i <= n; i++) {
cin >> u >> v;
num[u].push_back(v);
}
for (int i = ; i <= m; i++) {
if (num[i].size()) {
sort(num[i].begin(), num[i].end());
}
}
int ans = ;
for (int i = ; i <= m; i++) {
int len = num[i].size();
if (len) {
int sum = ;
for (int j = ; j < len; j++) {
sum += num[i][len - j - ];
//cout<<i<<" "<<j<<" "<<sum<<endl;
if (sum > ) {
pre[j + ] += sum;
} else {
break;
}
}
}
}
for (int i = ; i <= ; i++) {
ans = max(ans, pre[i]);
}
cout << ans << endl;
}
D
构造题 毛毛虫图
#include<bits/stdc++.h>
using namespace std;
const int MAXN = ;
inline void read(int &v) {
v = ;
char c = ;
int p = ;
while (c < '' || c > '') {
if (c == '-') {
p = -;
}
c = getchar();
}
while (c >= '' && c <= '') {
v = (v << ) + (v << ) + c - '';
c = getchar();
}
v *= p;
}
int n, m, a[MAXN], b[MAXN], f[MAXN], s[MAXN], t[MAXN], an, sm, T, z;
int main() {
int i, j = , a1, a2, e = ;
read(n);
for (int i = ; i <= n; i++) {
read(a[i]);
sm += a[i];
}
if (sm < n * - ) {
cout << "NO" << endl;
return ;
}
for (int i = ; i <= n; i++) {
if (a[i] >= ) {
f[i] = ;
b[++z] = i;
if (z >= ) {
s[z] = b[z - ];
t[z] = i;
}
}
}
for (int i = ; i <= z; i++) {
a[b[i]] -= (i != ) + (i != z);
}
cout << "YES " << min(z + , n - ) << endl << n - << endl;
for (int i = ; i <= n; i++) {
if (a[i] == && !f[i]) {
if (!e) {
e = ;
a[b[z]]--;
s[++z] = i;
t[z] = b[z - ];
} else {
for (; !a[b[j]]; j++);
a[b[j]]--;
s[++z] = i;
t[z] = b[j];
}
}
}
for (int i = ; i <= n; i++) {
cout << s[i] << " " << t[i] << endl;
}
}
G
把每条边当做一个点 搞最大权闭合子图即可
//Netflow dumpling
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = ;
const int MAXM = ;
const ll INF = ;
ll Head[MAXN], cur[MAXN], lev[MAXN], to[MAXM << ], nxt[MAXM << ], ed, S, T;
ll f[MAXM << ];
inline void addedge(int u, int v, ll cap)
{
to[++ed] = v;
nxt[ed] = Head[u];
Head[u] = ed;
f[ed] = cap;
to[++ed] = u;
nxt[ed] = Head[v];
Head[v] = ed;
f[ed] = ;
return;
}
inline bool BFS()
{
int u;
memset(lev, -, sizeof(lev));
queue<int>q;
lev[S] = ;
q.push(S);
while (q.size()) {
u = q.front();
q.pop();
for (int i = Head[u]; i; i = nxt[i])
if (f[i] && lev[to[i]] == -) {
lev[to[i]] = lev[u] + ;
q.push(to[i]);
/*
if (to[i] == T)
{
return 1;
}
magic one way optimize
*/
}
}
memcpy(cur, Head, sizeof Head);
return lev[T] != -;
}
inline ll DFS(int u, ll maxf)
{
if (u == T || !maxf) {
return maxf;
}
ll cnt = ;
for (ll &i = cur[u], tem; i; i = nxt[i])
if (f[i] && lev[to[i]] == lev[u] + ) {
tem = DFS(to[i], min(maxf, f[i]));
maxf -= tem;
f[i] -= tem;
f[i ^ ] += tem;
cnt += tem;
if (!maxf) {
break;
}
}
if (!cnt) {
lev[u] = -;
}
return cnt;
}
ll Dinic()
{
ll ans = ;
while (BFS()) {
ans += DFS(S, INF);
}
return ans;
}
void init(int SS, int TT)
{
memset(Head, , sizeof(Head));
ed = ;
S = SS;
T = TT;
return;
}
int main()
{
ios_base::sync_with_stdio();
cin.tie();
int n, m;
ll u, v, c;
cin >> n >> m;
init(, n + m + );
for (int i = ; i <= n; i++) {
cin >> c;
addedge(m + i, T, c);
}
ll summ = ;
for (int i = ; i <= m; i++) {
cin >> u >> v >> c;
summ += c;
addedge(S, i, c);
addedge(i, m + u, INF);
addedge(i, m + v, INF);
}
cout << summ - Dinic() << endl;
return ;
}