Educational Codeforces Round 61

今早刚刚说我适合打pikmike出的EDU

然后我就挂了

A

不管

B

不管

C

这道题到快结束了才调出来

大概就是\(n^2\)枚举不选的区间

然后随便搞搞？

大体就是维护一下区间\(1\)的个数和\(2\)的个数

判断枚举的区间有没有交集

这个的答案就是并集1的个数和交集2的个数

用总的减去更新就好了

另外如果一个区间被另外一个区间完全包含

那么这个区间肯定是没用的

特判一下就好了

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<ctime>
#include<cmath>
#define LL long long
#define pii pair<int,int>
#define mk make_pair
#define fi first
#define se second
using namespace std;
const int N = 5005;
struct node{
    int xi;
    int yi; 
}a[N],b[N];
int n,q;
int sum[N];
int num2[N];
int num1[N];
bool book[N];
int tot;
int ans;
int cnt;
inline bool cmp(node x,node y){
    if(x.xi != y.xi)
    return x.xi < y.xi;
    return x.yi < y.yi; 
}
inline int read(){
    int v = 0,c = 1;char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') c = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        v = v * 10 + ch - 48;
        ch = getchar();
    }
    return v * c;
}
inline bool jiao(int x,int y){
    return a[x].yi >= a[y].xi;
}
int main(){
    n = read(),q = read();
    for(int i = 1;i <= q;++i){
        a[i].xi = read();
        a[i].yi = read();
    }
    sort(a + 1,a + q + 1,cmp);
    for(int i = 1;i <= q;++i){
        bool flag = 0;
        for(int j = 1;j <= q;++j){
            if(j == i || book[j]) continue;
            if(a[j].xi <= a[i].xi && a[j].yi >= a[i].yi) flag = 1;
        }
        if(!flag) b[++cnt] = a[i];
        else book[i] = 1;
    }
    sort(b + 1,b + cnt + 1,cmp);
    for(int i = 1;i <= cnt;++i){
        for(int j = b[i].xi;j <= b[i].yi;++j) sum[j]++; 
    } 
    for(int i = 1;i <= n;++i){
        num1[i] = num1[i - 1] + (sum[i] == 1);
        num2[i] = num2[i - 1] + (sum[i] == 2);
        if(sum[i]) tot++;
    }
    if(cnt <= q - 2){printf("%d\n",tot);return 0;}
    if(cnt == q - 1){
        for(int i = 1;i <= cnt;++i){
            ans = max(ans,tot - (num1[b[i].yi] - num1[b[i].xi - 1]));
        }
        cout << ans;
        return 0;
    }
    for(int i = 1;i <= cnt;++i){
        for(int j = i + 1;j <= cnt;++j){
            int x = i,y = j;
            if(jiao(x,y)){
                ans = max(ans,tot - (num2[b[x].yi] - num2[b[y].xi - 1])
                 - (num1[b[y].yi] - num1[b[x].xi - 1]));    
            }
            else{
                ans = max(ans,tot - (num1[b[y].yi] - num1[b[y].xi - 1]) - (num1[b[x].yi] - num1[b[x].xi - 1])); 
            }
        }
    }
    cout << ans;
    return 0;
}

D

很明显,答案具有可二分性

我们二分答案之后,实质上就变成了一个贪心

维护一个堆

我们枚举时间轴

然后每次弹出需要充电的时间轴最靠前的元素，每次给他充电

这样时间复杂度为\(O(n + k)*log(ans)*log(n)\)

我凭着这个算法成功卡进了最劣解第一名

这种算法可能有点卡常

我们优化一下

发现堆得本质是为了取出当前时间最靠前的

而时间这个东西又是单调不降的

我们就可以开vector来维护

同时对于时间维护一个指针,表示当前时间点

顺着指针扫就好了

每次从vector里面搞出来一个,然后把他放在应该在的位置

这样时间复杂度就变成了

\(O((n + k)log(ans))\)

就不会被卡常了

只放一下两个log的代码

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<ctime>
#include<cmath>
#define LL long long
#define pii pair<int,int>
#define mk make_pair
#define fi first
#define se second
using namespace std;
const int N = 3e5 + 3;
LL a[N],b[N];
LL c[N];
LL n,m,k;
struct node{
    LL rest;
    int id;
    LL outt;
    LL intt;
};
bool operator < (node x,node y){
    return x.outt > y.outt;
}
inline LL read(){
    LL v = 0,c = 1;char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') c = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        v = v * 10 + ch - 48;
        ch = getchar();
    }
    return v * c;
}
inline bool check(LL mid){
    priority_queue <node> q;
    for(int i = 1;i <= n;++i) q.push((node){a[i] - b[i] * c[i],i,c[i],0});
    for(int i = 1;i < k;++i){
        node x = q.top();int id = x.id;q.pop(); 
        if(x.outt > k) break;
        if(x.outt < i) return 0;
        if(x.rest + mid + (x.outt - i) * b[id] < 0) return 0;
        LL re = x.rest + mid + (x.outt - i) * b[id];
        LL cc = re / b[id] + 1;
        q.push((node){re - cc * b[id],id,cc + i,i});
    }
    if(n == 1){
        if(q.top().outt < k) return 0;
        if(q.top().outt > k) return 1;
        if(q.top().rest + mid < 0) return 0;    
    }
    else{
        if(q.top().outt < k) return 0;  
        if(q.top().outt > k) return 1;
        if(q.top().rest + mid < 0) return 0;
        q.pop();
        if(q.top().outt <= k) return 0;
    }
    return 1;
}
int main(){
    
    n = read(),k = read() - 1;
    for(int i = 1;i <= n;++i) a[i] = read();
    for(int i = 1;i <= n;++i){
        b[i] = read();
        c[i] = a[i] / b[i] + 1;
    }
    sort(c + 1,c + n + 1);
    for(int i = 1;i <= n;++i){
        if(c[i] < i){
            printf("-1\n");
            return 0;
        }
    }
    LL l = 0,r = 1e13,ans;
    for(int i = 1;i <= n;++i) c[i] = a[i] / b[i] + 1; 
    while(l <= r){
        LL mid = (l + r) >> 1;
        if(check(mid)) r = mid - 1,ans = mid;
        else l = mid + 1;
    }
    printf("%lld\n",ans);
    return 0;
}

F

区间DP

我们设\(f_{l,r}\)表示吧\([l,r]\)这个区间全部删完的最小次数

对于\(s[l]\)我们考虑是把他和区间内的某个一起删还是单独删
\[ dp_{l , r} = \min(dp_{l + 1,r} + 1,\min_{l<i <= r,s[i] == s[l]}dp_{l,i - 1} + dp_{i,j}) \]

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<ctime>
#include<cmath>
#define LL long long
#define pii pair<int,int>
#define mk make_pair
#define fi first
#define se second
using namespace std;
const int N = 505;
int f[N][N];
int n;
char s[N];
inline int read(){
    int v = 0,c = 1;char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') c = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        v = v * 10 + ch - 48;
        ch = getchar();
    }
    return v * c;
}
int main(){
    memset(f,0x3f,sizeof(f));
    n = read();
    scanf("%s",s + 1);
    for(int i = 1;i <= n;++i){
        f[i][i] = 1;
        f[i][i - 1] = 0;
    }
    f[n + 1][n] = 0;
    for(int len = 2;len <= n;++len){
        for(int i = 1;i <= n;++i){
            int j = i + len - 1;
            if(j > n) continue;
            f[i][j] = min(f[i][j],1 + f[i + 1][j]);
            for(int h = i + 1;h <= j;++h) 
            if(s[i] == s[h]) f[i][j] = min(f[i][j],f[i + 1][h - 1] + f[h][j]);
        }
    }
    cout << f[1][n];
    return 0;
}