# Educational Codeforces Round 58 (Rated for Div. 2) (题解)

C题卡了一个小时, 又被教育场教育了...

#include <iostream>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;

int main() {
int t;
scanf("%d", &t);
REP(i,1,t) {
int l,r,d;
scanf("%d%d%d", &l, &r, &d);
if (d<l) printf("%d\n",d);
else printf("%d\n", r/d*d+d);
}
}

#include <iostream>
#include <string.h>
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
const int N = 5e5+10;
char s[N];
int f[N];

int main() {
scanf("%s", s+1);
int n = strlen(s+1);
REP(i,1,n) f[i]=f[i-1]+(s[i]==‘|‘);
int L = 0, R = 0;
REP(i,1,n) {
if (!L&&s[i]==‘[‘) L = i;
if (L&&s[i]==‘:‘) {
L = i;
break;
}
}
PER(i,1,n) {
if (!R&&s[i]==‘]‘) R = i;
if (R&&s[i]==‘:‘) {
R = i;
break;
}
}
if (!L||L>=R) return puts("-1"),0;
printf("%d\n",4+f[R]-f[L]);
}

#include <iostream>
#include <algorithm>
#include <string.h>
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
const int N = 5e5+10;
char s[N];
int n;
int L[N], R[N], f[N], c[N], q[N];

int id(int x) {
return lower_bound(f+1,f+1+*f,x)-f;
}

void work() {
scanf("%d", &n);
*f = 0;
REP(i,1,n) {
scanf("%d%d", L+i, R+i);
L[i]*=2, R[i]*=2;
f[++*f] = L[i];
f[++*f] = L[i]+1;
f[++*f] = R[i];
f[++*f] = R[i]+1;
}
sort(f+1,f+1+*f),*f=unique(f+1,f+1+*f)-f-1;
*q = 0;
REP(i,1,n) {
++c[id(L[i])],--c[id(R[i]+1)];
q[++*q] = id(L[i]);
q[++*q] = id(R[i]+1);
}
sort(L+1,L+1+n);
int sum = 0, ok = 0;
REP(i,1,*f) {
sum += c[i];
if (!sum) {
int t = *lower_bound(L+1,L+1+n,f[i]);
if (t>f[i]) {
REP(j,1,n) {
printf("%d ",R[j]<f[i]?1:2);
}
ok = 1;
printf("\n");
break;
}
}
}
if (!ok) puts("-1");
REP(i,1,*q) c[q[i]] = 0;
}

int main() {
int t;
scanf("%d", &t);
REP(i,1,t) work();
}

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <string.h>
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define x first
#define y second
using namespace std;

int gcd(int x, int y) {return y?gcd(y,x%y):x;}

const int N = 5e5+10;
int n, ans;
int a[N];
vector<int> g[N];
map<int,int> dp[N];

void dfs(int x, int fa) {
for (int y:g[x]) if (y!=fa) {
dfs(y,x);
//先考虑子树间转移
for (auto f1:dp[y]) {
int g1 = gcd(f1.x,a[x]);
if (g1<=1) continue;
for (auto f2:dp[x]) {
int g2 = gcd(f2.x,g1);
if (g2<=1) continue;
ans = max(ans, f1.y+f2.y);
}
}
//最后再用子树更新x
for (auto f1:dp[y]) {
int g1 = gcd(f1.x,a[x]);
if (g1<=1) continue;
ans = max(ans, f1.y+1);
dp[x][g1] = max(dp[x][g1], f1.y+1);
}
}
dp[x][a[x]] = max(dp[x][a[x]],1);
}

int main() {
scanf("%d", &n);
REP(i,1,n) {
scanf("%d", a+i);
if (a[i]>1) ans=1;
}
REP(i,2,n) {
int u, v;
scanf("%d%d", &u, &v);
//这里优化一下
if (gcd(a[u],a[v])>1) {
g[u].push_back(v);
g[v].push_back(u);
}
}
REP(i,1,n) {
if (dp[i].empty()) dfs(i,0);
}
printf("%d\n", ans);
}

#include <iostream>
#include <algorithm>
#define REP(i,a,b) for(int i=a;i<=b;++i)
using namespace std;

int main() {
int n;
scanf("%d", &n);
int a=0, b=0;
REP(i,1,n) {
char op;
int x, y;
scanf(" %c%d%d", &op, &x, &y);
if (x>y) swap(x,y);
if (op==‘+‘) a=max(a,x),b=max(b,y);
else puts(x>=a&&y>=b?"YES":"NO");
}
}

$dp[k][i][j]$为预处理出加$k$次油从$i$到$j$时, 每次加油后行驶的最大距离的最小值

#include <iostream>
#include <algorithm>
#define REP(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
typedef long long ll;

const int N = 401;
int n, m;
int dp[N][N][N];
int a[N];

int main() {
scanf("%d%d", &n, &m);
REP(i,1,n) scanf("%d", a+i);
REP(i,1,n) REP(j,i,n) dp[0][i][j]=a[j]-a[i];
REP(k,1,n) REP(i,1,n) {
int now = i;
REP(j,i,n) {
while (now<j&&max(dp[k-1][i][now],a[j]-a[now])>max(dp[k-1][i][now+1],a[j]-a[now+1])) ++now;
dp[k][i][j] = max(dp[k-1][i][now], a[j]-a[now]);
}
}
ll ans = 0;
REP(i,1,m) {
int s,f,c,r;
scanf("%d%d%d%d",&s,&f,&c,&r);
ans = max(ans,(ll)dp[r][s][f]*c);
}
printf("%lld\n", ans);
}

$xor$的性质还是太弱了啊, 没有什么单调性, 一般直接考虑线性基, 或者$trie$上贪心就好了

#include <iostream>
#include <algorithm>
#define REP(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
int a[50], n;

int main() {
scanf("%d", &n);
int sum = 0, t;
REP(i,1,n) {
scanf("%d", &t);
sum ^= t;
REP(j,1,*a) t = min(t,t^a[j]);
if (t) a[++*a]=t;
}
printf("%d\n", sum?*a:-1);
}

Educational Codeforces Round 58 (Rated for Div. 2) (题解)

(0)
(0)

0条