Codeforces Round #552 (Div. 3)

休闲VP发现打的真的太休闲了,完全没有比赛的氛围

A,B

不管

C

暴力跑第一轮和最后一轮

中间的轮数直接做除法

#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;
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;
}
LL aaa,bbb,ccc;
LL ans;
int aa[5],bb[5],cc[5];
inline LL work(LL x,LL a,LL b,LL c){
    for(int j = x;j <= 7;++j){
        if(j == 1 || j == 4 || j == 7) a--;
        if(j == 2 || j == 6) b--;
        if(j == 3 || j == 5) c--;
        if(a < 0 || b < 0 || c < 0) return j - x;   
    }
    LL week,day;
    LL resta = a / 3;
    LL restb = b / 2;
    LL restc = c / 2;
    week = min(resta,min(restb,restc));
    LL ans = week * 7 + 7 - x + 1;
    a = a - week * 3,b -= week * 2,c -= week * 2;
    for(int j = 1;j <= 7;++j){
        if(j == 1 || j == 4 || j == 7) a--;
        if(j == 2 || j == 6) b--;
        if(j == 3 || j == 5) c--;
        ans++;
        if(a < 0 || b < 0 || c < 0) return ans - 1;
    }
    for(int j = 1;j <= 7;++j){
        if(j == 1 || j == 4 || j == 7) a--;
        if(j == 2 || j == 6) b--;
        if(j == 3 || j == 5) c--;
        ans++;
        if(a < 0 || b < 0 || c < 0) return ans - 1;
    }
}
int main(){
    cin >> aaa >> bbb >> ccc;
    aa[1] = 4,aa[2] = 7,aa[3] = 8; 
    bb[1] = 6,bb[2] = 9;
    cc[1] = 5,cc[2] = 10;
    for(int i = 1;i <= 7;++i){
        ans = max(ans,work(i,aaa,bbb,ccc));
    //  printf("%d %d\n",i,ans);
    }
    cout << ans;
    return 0;
}

D

之前贪心发现贪错了

发现操作分位3种

\(x-1\),\(y - 1\),\(x-1,y+1\)

可以证明当\(s[i] = 1\)时,使用\(x - 1,y+1\)一定不会更劣

所以就尽可能的在\(s[i] = 1\)时使用\(x\)就好了

#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 = 2e5 + 3;
int s[N];
int n,a,b,num;//b：太阳能 
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(){
    n = read(),a = read(),b = read(),num = 0;
    int rest = b;
    for(int i = 1;i <= n;++i) s[i] = read();
    for(int i = 1;i <= n;++i){
        if(a == 0 && rest == 0) {printf("%d\n",i - 1);return 0;}
        if(s[i] == 0 && rest != 0) rest--;
        else if(s[i] == 0 && rest == 0) a--;
        else if(s[i] == 1 && rest != b){
            if(a == 0) rest--;
            else {
                a--;
                if(rest != 0) num++;
                rest++; 
            }   
        }
        else if(s[i] == 1 && rest == b){
            rest--;
        }
//      printf("%d %d\n",a,rest);
    }
    printf("%d\n",n);
    return 0;
}
/*
19 7 4
0 0 1 1 0 1 0 0 1 0 1 1 1 1 1 1 0 0 1
*/

E

直接用双向链表模拟就好了

时间复杂度可以证明

暴力删除

懒得写链表,就用set维护

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<ctime>
#include<set>
#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 = 2e5 + 3;
int a[N];
int L[N];
int R[N];
bool book[N];
int n,k;
int ans[N];
set<pii> s;
set<int> ss; 
int sta[N];
int tot;
set<pii>::iterator it;
set<int>::iterator iit;
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(){
    int now = 1;
    n = read(),k = read();
    for(int i = 1;i <= n;++i) a[i] = read(),s.insert(mk(a[i],i)),ss.insert(i);
    while(!s.empty()){
        it = s.end();it--;
        pii x = *it;
        tot = 0;
        iit = ss.lower_bound(x.se);
        for(int num = 0;num <= k;--iit,++num){
        //  printf("%d ",*iit);
            ans[*iit] = now;
            s.erase(mk(a[*iit],*iit));
            sta[++tot] = *iit;
            if(iit == ss.begin()) break;
        }
        iit = ss.lower_bound(x.se);
        for(int num = 0;num <= k && iit != ss.end();++iit,++num){
        //  printf("%d ",*iit);
            ans[*iit] = now;
            s.erase(mk(a[*iit],*iit));
            sta[++tot] = *iit;  
        }
    //  puts("");
        for(int i = 1;i <= tot;++i) ss.erase(sta[i]);
        if(now == 1) now = 2;
        else now = 1;
    }
    for(int i = 1;i <= n;++i) printf("%d",ans[i]);
    return 0;
}

F

发现\(k\)这么小,肯定有东西

发现购买的物品一定是前\(k\)

前\(k\)小一定是从大往小买

直接排序

所以我们设\(f_i\)表示前\(i\)个物品的最小花费

每次枚举用了哪一个优惠

或者不用优惠就好了

#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 = 2e5 + 3;
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 n,k,m;
int bar[N];
int f[N];
int a[N];
int sum[N];
int main(){
    n = read(),m = read(),k = read();
    for(int i = 1;i <= n;++i) a[i] = read();
    for(int i = 1;i <= m;++i){
        int x = read(),y = read();
        bar[x] = max(bar[x],y); 
    }
    sort(a + 1,a + n + 1);
    reverse(a + 1,a + k + 1);
    for(int i = 1;i <= k;++i) sum[i] = sum[i - 1] + a[i];
    memset(f,0x3f,sizeof(f));
    f[0] = 0;
//  for(int i = 1;i <= k;++i) printf("%d\n",a[i]);
    for(int i = 1;i <= k;++i){
        for(int j = 1;j <= i;++j)
            f[i] = min(f[i],f[i - j] + sum[i] - sum[i - j] - (sum[i] - sum[i - bar[j]]));       
        f[i] = min(f[i],f[i - 1] + a[i]);
    }
    cout << f[k] << endl;
    return 0;
}

G

\[ lcm(i,j) = \frac{i\times j}{gcd(i,j)} \]

我们就枚举\(gcd(i,j)\)

显然\(i,j\)都要是他的倍数

在枚举的时候顺带更新答案就好了

CF上开\(4\)s,\(10^7\)一个\(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 = 1e7 + 3;
const int M = 1e7;
int n;
int a[N];
LL ans = 9999999999999999;
pii id;
int vis[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(){
    n = read();
    for(int i = 1;i <= n;++i){
        a[i] = read();
        if(vis[a[i]]){
            if(a[i] < ans) ans = a[i],id = mk(vis[a[i]],i); 
        }
        vis[a[i]] = i;
    }
    for(int d = 1;d <= M;++d){
        int maxx1 = 0,maxx2 = 0;
        for(int x = d;x <= M;x += d){
            if(vis[x]){
                if(!maxx1) maxx1 = vis[x];
                else if(!maxx2) maxx2 = vis[x];
                else maxx2 = maxx1,maxx1 = vis[x];
                if(maxx1 != 0 && maxx2 != 0)
                if(1ll * a[maxx1] * a[maxx2] / d < ans) ans = 1ll * a[maxx1] * a[maxx2] / d,id = mk(maxx1,maxx2);
            //  printf("%d %d %d %lld\n",d,maxx1,maxx2,ans);
            }
        }
    }
    if(id.fi > id.se) swap(id.fi,id.se);
    printf("%d %d\n",id.fi,id.se);
    return 0;
}