首页 > 其他 > 详细

【AtCoder】AGC011

时间：2019-05-03 00:27:42      阅读：130      评论：0      收藏：0      [点我收藏+]

AGC011

A - Airport Bus

大意：有N个人，每个人只能在\([T_i,T_i +K]\)这段区间乘车，每辆车安排C人，问最少安排几辆车

直接扫，遇到一个没有车的在\(T_i +K\)分配一辆

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
#include <queue>
#define enter putchar('\n')
#define space putchar(' ')
//#define ivorysi
#define pb push_back
#define mo 974711
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define MAXN 500005
#define eps 1e-12
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < '0' || c > '9') {
    if(c == '-') f = -1;
    c = getchar();
    }
    while(c >= '0' && c <= '9') {
    res = res * 10 - '0' + c;
    c = getchar();
    }
    res = res * f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) out(x / 10);
    putchar('0' + x % 10);
}
int N,C,K;
int T[1000005];
void Solve() {
    read(N);read(C);read(K);
    for(int i = 1 ; i <= N ; ++i) read(T[i]);
    sort(T + 1,T + N + 1);
    int ans = 0;
    int cnt = 0,t = 0;
    for(int i = 1 ; i <= N ; ++i) {
    if(t < T[i] || !cnt) {
        ++ans;
        t = T[i] + K;
        cnt = C;
    }
    --cnt;
    }
    out(ans);enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
}

B - Colorful Creatures

大意：N个怪兽颜色两两不同，两个怪物如果一个大小是A颜色是B，一个大小是C（C <= 2 * A）颜色是D，新怪物可以是大小A+C，颜色是B，问最后可能是几种颜色

直接二分找满足要求的数的位置，然后能扩到的最大体积就是从最小的数到这个数的前缀和，每次至少扩大两倍，所以只用log次

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
#include <queue>
#define enter putchar('\n')
#define space putchar(' ')
//#define ivorysi
#define pb push_back
#define mo 974711
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define MAXN 500005
#define eps 1e-12
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < '0' || c > '9') {
    if(c == '-') f = -1;
    c = getchar();
    }
    while(c >= '0' && c <= '9') {
    res = res * 10 - '0' + c;
    c = getchar();
    }
    res = res * f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) out(x / 10);
    putchar('0' + x % 10);
}
int N;
int64 A[100005],tmp[100005],sum[1000005];
void Solve() {
    read(N);
    for(int i = 1 ; i <= N ; ++i) {
    read(A[i]);
    tmp[i] = A[i];
    }
    tmp[N + 1] = 1000000001;
    sort(tmp + 1,tmp + N + 2);
    int ans = 0;
    for(int i = 1 ; i <= N ; ++i) {
    sum[i] = sum[i - 1] + tmp[i]; 
    }
    for(int i = 1 ; i <= N ; ++i) {
    if(2 * A[i] >= tmp[N]) {++ans;continue;}
    int t = lower_bound(tmp + 1,tmp + N + 2,2 * A[i] + 1) - tmp - 1;
    while(1) {
        if(2 * sum[t] >= tmp[N]) {++ans;break;}
        int p = lower_bound(tmp + 1,tmp + N + 2,sum[t] * 2 + 1) - tmp - 1;
        if(p == t) break;
        t = p;
    }
    }
    out(ans);enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
}

C - Squared Graph

大意是给出一张图，然后建一张新图，新图的点标号是(a,b)
如果a和c有一条边，b和d有一条边，那么(a,b)和(c,d)之间有一条边

我们把这道题当成这道题来做，给出两张图，如果第一张图有边(a,c)，第二张图有边(b,d),那么第三张图上有边(a,b)(c,d)

如果某张图只有一个点，那么答案就是另一张图的点数

然后我们发现对于某两个点对第一张图(a,c)，第二张图(b,d)如果有一条长度为L的路径，那么第三张图(a,b)(c,d)一定可以联通
但是我们发现我们经过的路径可以不是简单路径，也就是我们反复走一条边，那么我们只和路径长度的奇偶性有关了

很容易想到二分图，如果两张图都是二分图且联通的话，那么第三张图联通分量的个数是2
分别是\(S_a * T_b \cup T_a * S_b\)和\(S_a * S_b \cup T_a * T_b\)

而两张图都是非二分图且联通的话，任意路径的奇偶性都可以互相转化，所以整张图就是一个联通块
那么我们求出两个图的孤立点个数\(i_A,i_B\)，两个图的非二分图联通块个数\(p_A,p_B\)，两个图的二分图联通块个数\(q_A,q_B\)
答案就是
\(i_Ai_B + i_A(N_B - i_B) + i_B(N_A - i_A) + p_Ap_B + p_Aq_B + p_Bq_A + 2q_Aq_B\)

代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
#include <queue>
#define enter putchar('\n')
#define space putchar(' ')
//#define ivorysi
#define pb push_back
#define mo 974711
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define MAXN 200005
#define eps 1e-12
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < '0' || c > '9') {
    if(c == '-') f = -1;
    c = getchar();
    }
    while(c >= '0' && c <= '9') {
    res = res * 10 - '0' + c;
    c = getchar();
    }
    res = res * f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) out(x / 10);
    putchar('0' + x % 10);
}
int N,M,I,P,Q;
struct node {
    int next,to;
}E[MAXN * 2];
int head[MAXN],sumE,col[MAXN];
bool vis[MAXN];
void dfs(int u) {
    vis[u] = 1;
    for(int i = head[u] ; i ; i = E[i].next) {
    int v = E[i].to;
    if(!vis[v]) {
        dfs(v);
    }
    }
}
bool paint(int u) {
    if(!col[u]) col[u] = 2;
    for(int i = head[u] ; i; i = E[i].next) {
    int v = E[i].to;
    if(!col[v]) {col[v] = col[u] ^ 1;if(!paint(v)) return false;}
    else if(col[v] == col[u]) return false;
    }
    return true;
}
void add(int u,int v) {
    E[++sumE].to = v;
    E[sumE].next = head[u];
    head[u] = sumE;
}
void Solve() {
    read(N);read(M);
    int u,v;
    for(int i = 1 ; i <= M ; ++i) {
    read(u);read(v);
    add(u,v);add(v,u);
    }
    for(int i = 1 ; i <= N ; ++i) {
    if(!head[i]) ++I;
    else if(!vis[i]){
        dfs(i);
        if(paint(i)) ++Q;
        else ++P;
    }
    }
    int64 ans = 1LL * I * I + 2LL * I * (N - I);
    ans += 1LL * P * P + 2LL * P * Q + 2LL * Q * Q;
    out(ans);enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
}

D - Half Reflector

大意是n个管子排成一排，每个管子有两种状态，A状态是从某个方向进去，从原方向出来，B状态是从某个方向进去，从另一个方向出来
球经过一个A状态的管子这个管子会立刻变成B状态，经过一个B状态的管子会立刻变成A状态

往里面扔K个球，问最后管子的状态

我们发现如果第一个管子是A的话，球会立刻弹出去

否则的话
如果第二个管子是B
那么
A -> B
A A ->
如果第二个管子是A
A -> A
A <- B
B -> B
B A ->
也就是，每次操作后的状态只与右边第一个管子有关，并且最后一个管子一定是A
那么操作可以考虑成，删掉第一个字符，后面的字符全部取反，然后再最后填上一个A

然而有K次，我们发现起点移动N次之后就是循环了
如果N次之后是
BABABA...那么这个形态不会变

如果N次之后是
ABABAB...

那么之后的形态就是
BBABAB...
ABABAB...
这样的循环了

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
#include <queue>
#define enter putchar('\n')
#define space putchar(' ')
//#define ivorysi
#define pb push_back
#define mo 974711
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define MAXN 200005
#define eps 1e-12
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < '0' || c > '9') {
    if(c == '-') f = -1;
    c = getchar();
    }
    while(c >= '0' && c <= '9') {
    res = res * 10 - '0' + c;
    c = getchar();
    }
    res = res * f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) out(x / 10);
    putchar('0' + x % 10);
}
char s[MAXN];
int N,K,p = 1,num[MAXN],cnt,st;
void Solve() {
    read(N);read(K);
    scanf("%s",s + 1);
    for(int i = 1 ; i <= N ; ++i) num[i] = s[i] - 'A';
    st = num[1];
    while(K--) {
    if(st == 0) {st ^= 1;num[p] ^= 1;}
    else {
        ++p;++cnt;
        st = num[p];
        st ^= (cnt & 1);
    }
    if(p > N) break;
    }
    if(p <= N) {
    for(int i = p ; i <= N ; ++i) putchar('A' + (num[i] ^ (cnt & 1)));
    int t = N - (N - p + 1),c = (cnt - 1) & 1;
    while(t--) {
        putchar('A' + c);
        c ^= 1;
    }
    }
    else {
    if((cnt - 1) & 1) {
        for(int i = 1 ; i <= N ; ++i) putchar('A' + (i & 1));
    }
    else {
        putchar('A' + (K & 1));
        for(int i = 1 ; i < N ; ++i) putchar('A' + (i & 1));
    }
    }
    enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
}

E - Increasing Numbers

我们发现一个非下降的数字一定可以用不超过九个1111111111...1111表示

那么我们可以得到这样的一个式子，假如我们用了k个数，那么最多的话可以是这样的
\(N = \sum_{i = 1}^{9k} (10^{r_i} - 1) / 9\)
\(9N + 9k = \sum_{i = 1}^{9k} 10^{r_{i}}\)

我们只要每次计算出9N + 9 ，9N + 18...，然后看看十进制下每一位的数字和有没有超过9k，直接加的话最坏情况是一次操作\(O(L)\)的，但是大家应该都有种直觉总的操作就是\(O(L)\)的……就是势能分析啦，不太会证，就是一次长的进位过后之后不会再进位了。。。

复杂度\(O(lg N)\)

代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
#include <queue>
#define enter putchar('\n')
#define space putchar(' ')
//#define ivorysi
#define pb push_back
#define mo 974711
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define MAXN 200005
#define eps 1e-12
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < '0' || c > '9') {
    if(c == '-') f = -1;
    c = getchar();
    }
    while(c >= '0' && c <= '9') {
    res = res * 10 - '0' + c;
    c = getchar();
    }
    res = res * f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) out(x / 10);
    putchar('0' + x % 10);
}
struct Bignum {
    vector<int> v;
    int sum;
    Bignum operator = (string s) {
    v.clear();
    sum = 0;
    for(int i = s.length() - 1 ; i >= 0 ; --i) {
        v.pb(s[i] - '0');
        sum += s[i] - '0';
    }
    return *this;
    }
    friend Bignum operator * (const Bignum &a,const int b) {
    int s = a.v.size();
    Bignum c;c.v.clear();
    for(int i = 0 ; i <= s ; ++i) c.v.pb(0);
    int g = 0;
    for(int i = 0 ; i < s ; ++i) {
        int x = a.v[i] * b + g;
        c.v[i] = x % 10;
        g = x / 10;
    }
    if(g) c.v[s] = g;
    for(int i = s ; i > 0 ; --i) {
        if(c.v[i] == 0) c.v.pop_back();
        else break;
    }
    c.sum = 0;s = c.v.size();
    for(int i = 0 ; i < s ; ++i) c.sum += c.v[i];
    return c;
    }
}A;
string s;
void Solve() {
    cin>>s;
    A = s;
    A = A * 9;
    int ans = 0;
    while(1) {
    int s = A.v.size();
    int g = 9;
    for(int i = 0 ; i < s ; ++i) {
        if(!g) break;
        A.sum -= A.v[i];
        int x = A.v[i] + g;
        A.v[i] = x % 10;
        A.sum += A.v[i];
        g = x / 10;
    }
    if(g) A.v.pb(g),A.sum += g;
    ++ans;
    if(ans * 9 >= A.sum) break;
    }
    out(ans);enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
}

【AtCoder】AGC011

原文：https://www.cnblogs.com/ivorysi/p/10803917.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！