Southern and Volga Russia Qualifier 2019-2020 gym102348

190754 ワード
ACM_gymブラシ問題
文書ディレクトリ
  • A-Yellow Cards(思考)
  • B-Interesting Vertices(dfs遡及)
  • C-Marbles(状圧dp)
  • D-Ticket Game(思考ゲーム)
  • E-Painting The Fence(欲張り+優先キュー)
  • F-The Number of Products(暴力)
  • G-Swap Letters(思考)
  • H-Berland Prospect(リニアdp)
  • I-Radio Stations(2-sat+テクニック建図)
  • J-Monocarp and T-Shirts(期待+反発)
  • K-Moonbound(アナログ)
  • L-Printer(暴力)
    • A-Yellow Cards(思考)
    あなたに2つのチームをあげて、人数はそれぞれa 1、a 2 a 1、a 2 a 1、a 2 a 2、a 2で、すべてのチームはすべての人が最大でk 1、k 2 k 1、k 2 k 1、k 2枚のイエローカードを受け取った后に退場させられて、全部でn n n n枚のイエローカードがあって、最低と最大で何人が退場されますかを求めます.
    問題の構想を解く:貪欲に求めて、すべての人は同等に考えて、最も少ないのはすべての人が少なくともk−1 k−1枚のカードを受け取ってから場を離れて、最も多いのは優先的にk k kの値の小さい選手です.
    AC_code: 
    #include
#pragma GCC optimize(2)
#define bug printf("*********
    ");    
#define mem0(a) memset(a, 0, sizeof(a));
#define mem1(a) memset(a, -1, sizeof(a));
#define finf(a, n) fill(a, a+n, INF);
#define lowbit(x) x&-x
#define fuck(x) cout<
#define ios ios::sync_with_stdio(false);
#define pb(x) push_back(x)
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<LL, pair<int, LL> > LLppar;
typedef pair<int, int> par;
typedef pair<LL, int> LLpar;
const LL mod = 998244353;
const int inf = 1e9+7;
const LL INF = 1e18+7;
const int base = 131; //19260817 233 1331 1e9+7
const double eps = 0.000001;

int a1, a2, k1, k2, n;

int main() {
#ifndef ONLINE_JUDGE
    //freopen("out.txt", "w", stdout);
    //freopen("in.txt", "r", stdin);
#endif
    while(~scanf("%d%d%d%d%d", &a1, &a2, &k1, &k2, &n)) {
        int ans1 = max(0, n-a1*(k1-1)-a2*(k2-1)), ans2 = 0;
        if(k1 < k2) ans2 += min(a1, n/k1), n -= ans2*k1, ans2 += min(a2, n/k2);
        else ans2 += min(a2, n/k2), n -= ans2*k2, ans2 += min(a1, n/k1);
        printf("%d %d
    "    , ans1, ans2);
    }
#ifndef ONLINE_JUDGE
    //cout <
#endif
    return 0;
}

    B-Interesting Vertices(dfs遡及)
    あなたに1課n n n個の節点の木があって、その中にk k個の節点が染色されて、どれだけの節点が自分が染色されていないことを満たして、そのすべての本の木の中で少なくとも1つの節点が染色されていることを求めます.
    解題構想:d f s dfs dfs遡及は木の重心を求めるように解く.d f s dfs dfs遡及は各ノードのそのサブツリーに染色点があるかどうかを得ることができ、すべてのサブツリーにおける染色点の個数s u m sumを統計し、父に向かうサブツリーに染色された点数はk−s u m k−sum−sumである.これにより,このノードが条件を満たすか否かを判断できる.
    AC_code: 
    #include
 
#pragma GCC optimize(2)
#define bug printf("*********
    ");    
#define mem0(a) memset(a, 0, sizeof(a));
#define mem1(a) memset(a, -1, sizeof(a));
#define finf(a, n) fill(a, a+n, INF);
#define lowbit(x) x&-x
#define fuck(x) cout<
#define ios ios::sync_with_stdio(false);
#define pb(x) push_back(x)
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<LL, pair<int, LL> > LLppar;
typedef pair<int, int> par;
typedef pair<LL, int> LLpar;
const LL mod = 1e9 + 7;
const int inf = 1e9 + 7;
const LL INF = 1e18 + 7;
const int base = 131; //19260817 233 1331 1e9+7
const double eps = 0.000001;
 
int n, k, cnt;
int c[200010], head[200010], vis[200010], sz[200010];
 
struct edge {
    int to, nxt;
}e[200010*2];
 
void add(int u, int v) {
    e[cnt].to = v;
    e[cnt].nxt = head[u];
    head[u] = cnt ++;
}
 
vector<int> ans;
 
void dfs(int u) {
    vis[u] = 1;
    sz[u] = c[u];
    int flag = 1;
    for(int i = head[u]; ~i; i = e[i].nxt) {
        int en = e[i].to;
        if(vis[en]) continue;
        dfs(en);
        if(!sz[en]) flag = 0;
        sz[u] += sz[en];
    }
    if(!c[u] && flag && (k > sz[u] || u == 1)) ans.push_back(u);
}
 
int main() {
    int x, y;
    while(~scanf("%d%d", &n, &k)) {
        mem0(vis);mem0(c);mem1(head);
        cnt = 0;
        ans.clear();
        for(int i = 0; i < k; i ++) {
            scanf("%d", &x);
            c[x] = 1;
        }
        for(int i = 0; i < n-1; i ++) {
            scanf("%d%d", &x, &y);
            add(x, y), add(y, x);
        }
        dfs(1);
        sort(ans.begin(), ans.end());
        printf("%d
    "    , ans.size());
        for(auto i : ans) {
            printf("%d ", i);
        }
        printf("
    "    );
    }
    return 0;
}

    C-Marbles(状圧dp)
    あなたに1つの配列をあげて、毎回あなたは隣接する2つの要素を选んで交换することができて、あなたに最も少ない交换の回数を求めて、これは配列のすべての同じ要素とすべて1つになります.
    解題構想:配列の要素は最大20 20 20個しかないので、20 20ビットの状圧d p dpでこの問題を解決することができ、d p[i]dp[i]dp[i]dp[i]はi i iの状態が表す数字がすでに1つになっており、前の最低交換回数にランクされていることを示している.転移は、d p[i]=m i n(d p[i],d p[i(1<AC_code: 
    #include
 
#pragma GCC optimize(2)
#define bug printf("*********
    ");    
#define mem0(a) memset(a, 0, sizeof(a));
#define mem1(a) memset(a, -1, sizeof(a));
#define finf(a, n) fill(a, a+n, INF);
#define lowbit(x) x&-x
#define fuck(x) cout<
#define ios ios::sync_with_stdio(false);
#define pb(x) push_back(x)
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<LL, pair<int, LL> > LLppar;
typedef pair<int, int> par;
typedef pair<LL, int> LLpar;
const LL mod = 1e9 + 7;
const int inf = 1e9 + 7;
const LL INF = 1e18 + 7;
const int base = 131; //19260817 233 1331 1e9+7
const double eps = 0.000001;
 
int n;
int a[400010];
LL dp[1<<20], cost[25][25], pre[25][400010], s[25];
int id[25];
int main() {
    while(~scanf("%d", &n)) {
        mem1(id);
        mem0(cost);
        mem0(pre);
        int cnt = 0;
        for(int i = 1; i <= n; i ++) {
            scanf("%d", &a[i]);
            if(id[a[i]] == -1) id[a[i]] = cnt ++;
        }
        for(int i = 0; i < cnt; i ++) {
            int now = 1;
            s[i] = 0;
            for(int j = 1; j <= n; j ++) {
                if(id[a[j]] == i) s[i] += abs(j-now ++);
            }
            //printf("%d %lld
    ", i, s[i]);    
        }
        for(int i = 0; i < cnt; i ++) {
            pre[i][0] = 0;
            for(int j = 1; j <= n; j ++) {
                pre[i][j] = pre[i][j-1] + (id[a[j]] == i);
            }
        }
        for(int i = 1; i <= n; i ++) {
            for(int j = 0; j < cnt; j ++) {
                if(id[a[i]] == j) continue;
                cost[id[a[i]]][j] += pre[j][n] - pre[j][i];
            }
        }
        for(int i = 0; i < cnt; i ++) {
            for(int j = 0; j < cnt; j ++) {
                //printf("cost[%d][%d] = %lld
    ", i, j, cost[i][j]);    
            }
        }
        dp[0] = 0;
        for(int i = 1; i < 1<<cnt; i ++) {
            dp[i] = INF;
            int sz = 0;
            for(int j = 0; j < cnt; j ++) {
                if(!(i&(1<<j))) continue;
                LL val = 0;
                for(int k = 0; k < cnt; k ++) {
                    if(!(i&(1<<k)) || k == j) continue;
                    val += cost[k][j];
                }
                dp[i] = min(dp[i], dp[i^(1<<j)] + s[j] - val);
            }
        }
        printf("%lld
    "    , dp[(1<<cnt)-1]);
    }
    return 0;
}

    D-Ticket Game(思考ゲーム)
    文字列をあげます.文字「0」~「9」と「?」「?」「?」を含みます.誰もが「?」?前後して0~9を記入し、Monocarpが先手で、最後の文字列の前半の数字と後半に等しい場合はBicarpが勝つ.
    問題を解く構想:1、まず「に対して」?前半のみ、または右半分のみの場合、Monocarpがどのように記入してもBicarpは2人に1つの疑問符を記入させた後、疑問符の半分を9 9 9 9 9増加させることができることが分かったので、両側に92、どちらにも疑問符がついているとき、このときの二人の強みは同じなので、元の状態を維持するしかありません(ある半分をどれだけ増やしたいのか、私はもう半分を増やして、あなたが望む状態を得られないようにします).だから、最後には必ずまた1の状態に戻ります.
    AC_code: 
    #include
 
#pragma GCC optimize(2)
#define bug printf("*********
    ");    
#define mem0(a) memset(a, 0, sizeof(a));
#define mem1(a) memset(a, -1, sizeof(a));
#define finf(a, n) fill(a, a+n, INF);
#define lowbit(x) x&-x
#define fuck(x) cout<
#define ios ios::sync_with_stdio(false);
#define pb(x) push_back(x)
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<LL, pair<int, LL> > LLppar;
typedef pair<int, int> par;
typedef pair<LL, int> LLpar;
const LL mod = 1e9 + 7;
const int inf = 1e9 + 7;
const LL INF = 1e18 + 7;
const int base = 131; //19260817 233 1331 1e9+7
const double eps = 0.000001;
 
int n;
char s[200010];
 
int main() {
    while(~scanf("%d", &n)) {
        scanf("%s", s);
        int s1 = 0, s2 = 0, a = 0, b = 0;
        for(int i = 0; i < n/2; i ++) {
            if(s[i] == '?') s1 ++;
            else a += s[i]-'0';
        }
        for(int i = n/2; i < n; i ++) {
            if(s[i] == '?') s2 ++;
            else b += s[i]-'0';
        }
        if(a-b == (s2-s1)/2*9) printf("Bicarp
    "    );
        else printf("Monocarp
    "    );
    }
    return 0;
}

    E-Painting The Fence(欲張り+優先キュー)
    あなたにm mのm种类の数字の全部でn n n个をあげて、あなたを前から后ろに埋めさせて、同じ数字は最大でk k个を连続して、あなたに构造の方案を出力させて、构造を构造することができません
    问题を解く考え方:贪欲な考え方、优先的に数量の多い先を选んで、このように最后に同じ数字の数量が最も少なくなることができて、だから私达は优先的に数量の最も多い2种类の数字を选んで埋めて、最后に残った(ある种)はその前の位置に埋めて、きっと同じと一绪に埋めて、ここは证明しないで、自分で描くことができます.優先キューシミュレーションでいいです.
    AC_code: 
    #include
 
#pragma GCC optimize(2)
#define bug printf("*********
    ");    
#define mem0(a) memset(a, 0, sizeof(a));
#define mem1(a) memset(a, -1, sizeof(a));
#define finf(a, n) fill(a, a+n, INF);
#define lowbit(x) x&-x
#define fuck(x) cout<
#define ios ios::sync_with_stdio(false);
#define pb(x) push_back(x)
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<LL, pair<int, LL> > LLppar;
typedef pair<int, int> par;
typedef pair<LL, int> LLpar;
const LL mod = 1e9 + 7;
const int inf = 1e9 + 7;
const LL INF = 1e18 + 7;
const int base = 131; //19260817 233 1331 1e9+7
const double eps = 0.000001;
 
int n, m, k;
int a[200010], s[200010];
 
struct node {
    int x, s;
    bool operator<(const node &a) const {
        return s < a.s;
    }
};
 
priority_queue<node> q;
 
int main() {
    int x;
    while(~scanf("%d%d%d", &n, &m, &k)) {
        mem0(s);
        mem0(a);
        while(!q.empty()) q.pop();
        for(int i = 1; i <= m; i ++) {
            node cur;
            scanf("%d", &cur.s);
            cur.x = i;
            q.push(cur);
        }
        int cnt = 0;
        while(!q.empty()) {
            if(q.size() >= 2) {
                node n1 = q.top();q.pop();
                node n2 = q.top();q.pop();
                a[cnt ++] = n1.x;
                a[cnt ++] = n2.x;
                n1.s --;
                n2.s --;
                if(n1.s) q.push(n1);
                if(n2.s) q.push(n2);
            }else {
                if(a[cnt-1] != q.top().x) {
                    a[cnt ++] = q.top().x;
                    node cur = q.top();q.pop();
                    cur.s --;
                    if(cur.s) q.push(cur);
                }
                break;
            }
        }
        for(int i = 0; i < cnt && !q.empty(); i ++) {
            if(a[i] == q.top().x) {
                s[i] += min(q.top().s, k-1);
                node cur = q.top();q.pop();
                cur.s -= min(cur.s, k-1);
                if(cur.s > 0) q.push(cur);
                else break;
            }
        }
        if(!q.empty()) printf("-1");
        else
        for(int i = 0; i < cnt; i ++) {
            for(int j = 0; j <= s[i]; j ++) {
                printf("%d ", a[i]);
            }
        }
        printf("
    "    );
    }
    return 0;
}

    F-The Number of Products(暴力)
    あなたに1つの配列をあげて、あなたに区間の積が負、ゼロ、正の個数になることを求めさせます.
    直接暴力で探せばいいので、おつりを探すときは気をつけてください.
    AC_code: 
    #include
 
#pragma GCC optimize(2)
#define bug printf("*********
    ");    
#define mem0(a) memset(a, 0, sizeof(a));
#define mem1(a) memset(a, -1, sizeof(a));
#define finf(a, n) fill(a, a+n, INF);
#define lowbit(x) x&-x
#define fuck(x) cout<
#define ios ios::sync_with_stdio(false);
#define pb(x) push_back(x)
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<LL, pair<int, LL> > LLppar;
typedef pair<int, int> par;
typedef pair<LL, int> LLpar;
const LL mod = 1e9 + 7;
const int inf = 1e9 + 7;
const LL INF = 1e18 + 7;
const int base = 131; //19260817 233 1331 1e9+7
const double eps = 0.000001;
 
int n;
int bit[200010];
int a[200010];
 
int main() {
    while(~scanf("%d", &n)) {
        LL ans1 = 0, ans2 = 0, ans3 = 0;
        int pre1 = 1, pre2 = 0, pre0 = 0, now = 1;
        for(int i = 1; i <= n; i ++) {
            scanf("%d", &a[i]);
            if(a[i] == 0) {
                pre1 = 1, pre2 = 0;
                now = 1;
                ans3 += 1LL*(i-pre0)*(n-i+1);
                pre0 = i;
                continue;
            }
            if(a[i] > 0) now *= 1;
            if(a[i] < 0) now *= -1;
            if(now > 0) ans1 += pre1, ans2 += pre2, pre1 ++;
            else ans1 += pre2, ans2 += pre1, pre2 ++;
        }
        printf("%lld %lld %lld
    "    , ans2, ans3, ans1);
    }
    return 0;
}

    G-Swap Letters(思考)
    あなたに2つの文字列をあげて、ただ‘a’’’’b’’‘a’’b’’’’’’’’‘a’’b’の2種類の文字だけあって、毎回操作してあなたはそれぞれ2つの文字列の中の2つの文字を選んで交換することができて、少なくとも何回の操作を聞いて2つの文字列を同じにすることができて、‘−1’‘−1’’’‘−1’’’’’’’’’’‘−1’’’’’’’’’’’’’’’
    問題を解く構想:貪欲に解いて、位置が同じで文字が同じで交換しないで、それでは最後にa b ab abあるいはb a ba baのこのような文字の対しか残っていません.2対の同じa b ab abあるいはb a baは1回の交換を通じてこの2対を同じにすることができて、1対のa b abとb a baは2回交換する必要があります.直接答えを統計すればいいです.
    AC_code: 
    #include
 
#pragma GCC optimize(2)
#define bug printf("*********
    ");    
#define mem0(a) memset(a, 0, sizeof(a));
#define mem1(a) memset(a, -1, sizeof(a));
#define finf(a, n) fill(a, a+n, INF);
#define lowbit(x) x&-x
#define fuck(x) cout<
#define ios ios::sync_with_stdio(false);
#define pb(x) push_back(x)
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<LL, pair<int, LL> > LLppar;
typedef pair<int, int> par;
typedef pair<LL, int> LLpar;
const LL mod = 1e9 + 7;
const int inf = 1e9 + 7;
const LL INF = 1e18 + 7;
const int base = 131; //19260817 233 1331 1e9+7
const double eps = 0.000001;
 
int n;
char s[200010], t[200010];
vector<int> v1, v2;
 
int main() {
    while(~scanf("%d", &n)) {
        scanf("%s%s", s, t);
        v1.clear(), v2.clear();
        for(int i = 0; i < n; i ++) {
            if(s[i] == t[i]) continue;
            if(s[i] == 'a') v1.push_back(i+1);
            else v2.push_back(i+1);
        }
        if(v1.size()%2 != v2.size()%2) printf("-1
    "    );
        else {
            int sum = v1.size()/2 + v2.size()/2 + v1.size()%2*2;
            printf("%d
    "    , sum);
            while(v1.size() >= 2) {
                printf("%d %d
    "    , v1[v1.size()-1], v1[v1.size()-2]);
                v1.pop_back();
                v1.pop_back();
            }
            while(v2.size() >= 2) {
                printf("%d %d
    "    , v2[v2.size()-1], v2[v2.size()-2]);
                v2.pop_back();
                v2.pop_back();
            }
            if(v1.size()) {
                printf("%d %d
    "    , v1[0], v1[0]);
                printf("%d %d
    "    , v1[0], v2[0]);
            }
        }
    }
    return 0;
}

    H-Berland Prospect(リニアdp)
    あなたに1つの増加する配列をあげて、あなたに1つの最も長い等差のシーケンスを探して、出力の長さ.
    解題構想:d p[i][j]dp[i][j]dp[i][j]dp[i][j]は位置i iから公差k=a[j]−a[i]k=a[j]−a[i]k=a[j]−a[i]k=a[j]−a[i]の最長シーケンスを表し、では、後ろから、d p[i][j]=m a x(d p[i][j],m a x(2,d p[j][i d d x[a[j]+k]+1))dp[i][j]=max(dp[i][j],max(2,dp[j][idx[a[j]+k]+1))dp[i][j]=max(dp[i]+j],max(2,dp[j]+idx[a[j]+k]+1))があり、最大値を記録すればよい.注意:この問題カードm a p Q A Q mapQQQQQQQQはm a p map mapでT T Tを離散化し、二分して下書きを探す必要がある.
    AC_code: 
    #include
 
#pragma GCC optimize(2)
#define bug printf("*********
    ");    
#define mem0(a) memset(a, 0, sizeof(a));
#define mem1(a) memset(a, -1, sizeof(a));
#define finf(a, n) fill(a, a+n, INF);
#define lowbit(x) x&-x
#define fuck(x) cout<
#define ios ios::sync_with_stdio(false);
#define pb(x) push_back(x)
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<LL, pair<int, LL> > LLppar;
typedef pair<int, int> par;
typedef pair<LL, int> LLpar;
const LL mod = 1e9 + 7;
const int inf = 1e9 + 7;
const LL INF = 1e18 + 7;
const int base = 131; //19260817 233 1331 1e9+7
const double eps = 0.000001;
 
int n;
LL x[3010];
int dp[3010][3010];
 
int main() {
    while(~scanf("%d", &n)) {
        mem0(dp);
        int cnt = 0;
        for(int i = 0; i < n; i ++) {
            scanf("%lld", &x[i]);
        }
        int ans = 2;
        for(int i = n-1; i >= 0; i --) {
            for(int j = i+1; j < n; j ++) {
                LL k = x[j]-x[i];
                int id = lower_bound(x, x+n, x[j]+k)-x;
                if(x[id] != x[j]+k) {
                    dp[i][j] = 2;continue;
                }
                dp[i][j] = max(dp[i][j], max(2, dp[j][id]+1));
                ans = max(ans, dp[i][j]);
                //printf("dp[%d][%d] = %d dp[%d][%d] = %d
    ", i, j, dp[i][j], j, id, dp[j][id]);    
            }
        }
        printf("%d
    "    , ans);
    }
    return 0;
}

    I-Radio Stations(2-sat+テクニック建図)
    n n n nの都市はラジオ局を配置しなければならなくて、第i iの都市は少なくともx i xiあるいはy i yi yi yi yiの中の1つをインストールしなければならなくて、次にあなたにp p p pのpのラジオ局をあげて、ラジオ局i i i i iの電力範囲はl i-r i li-ri li-ri riで、最後にmの制限条件があって、第i iの制限条件はラジオ局u i ui uiとv i viはすべてインストールすることができません最後に、n+m n+m n+mの条件を満たし、少なくとも1つの電力値f f f fが選択したk k局がl i<=f<=r i li<=f<=ri li<=f<=riを満たし、k k k kとf f f f f fを出力し、どのk局を選択したかを満たすように、局の設置案を見つけます.
    解題構想:電力範囲の制限がなければ、この問題は裸の2−s a t 2−sat 2−sat問題であり、現在電力範囲の制限があり、これらの制限条件も2−s a t 2−sat 2−sat 2−satのモデルに変換する必要がある.ここのn+m n+mの条件の連辺方式は私は言わない.主に電力範囲の連辺方式について話している.W∗2 W*2 W∗2点を再構築し、点i i iは条件f>=i f>=i f>=iを選択したことを示し、逆に点i+Wi+Wi+WはfAC_code: 
    #include
 
#pragma GCC optimize(2)
#define bug printf("*********
    ");    
#define mem0(a) memset(a, 0, sizeof(a));
#define mem1(a) memset(a, -1, sizeof(a));
#define finf(a, n) fill(a, a+n, INF);
#define lowbit(x) x&-x
#define fuck(x) cout<
#define ios ios::sync_with_stdio(false);
#define pb(x) push_back(x)
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<LL, pair<int, LL> > LLppar;
typedef pair<int, int> par;
typedef pair<LL, int> LLpar;
const LL mod = 998244353;
const int inf = 1e9 + 7;
const LL INF = 1e18 + 7;
const int base = 131; //19260817 233 1331 1e9+7
const double eps = 0.000001;
const int MX = 2e6+5;
 
int n, p, M, m;
int cnt, idx, scc, k, out;
int head[MX], dfn[MX], low[MX], instack[MX], belong[MX];
int pos[MX], du[MX], output[MX];
stack<int> st;
vector<int> v[MX];
 
struct edge {
    int to;
    int nxt;
}e[MX*6];
 
void add(int u, int v) {
    //printf("------%d %d
    ", u, v);    
    e[cnt].to = v;
    e[cnt].nxt = head[u];
    head[u] = cnt ++;
}
 
void tarjan(int k) {
    dfn[k] = low[k] = idx ++; ///idx    1
    instack[k] = 1;
    st.push(k);
    for(int i = head[k]; i != -1; i = e[i].nxt) {
        int en = e[i].to;
        if(!dfn[en]) {
            tarjan(en);
            low[k] = min(low[en], low[k]);
        } else if(instack[en]) {
            low[k] = min(low[k], dfn[en]);
        }
    }
    if(dfn[k] == low[k]) {
        scc ++; ///      (           )
        int v;
        do {
            v = st.top();
            st.pop();
            instack[v] = 0;
            belong[v] = scc;
        } while(k != v);
    }
}
 
int pt[MX];
 
void topo() {
    mem0(pt);
    queue<int> q;
    for(int i = 1; i <= scc; i ++) {
        if(du[i] == 0) q.push(i);
    }
    while(!q.empty()) {
        int u = q.front();q.pop();
        if(pt[u] == 0) {
            pt[u] = 1;
            pt[pos[u]] = 2;
        }
        for(int i = 0; i < v[u].size(); i ++) {
            int en = v[u][i];
            du[en] --;
            if(du[en] == 0) q.push(en);
        }
    }
    out = 0;
    for(int i = 1; i <= p; i ++) {
        if(pt[belong[i]] == 1) output[out ++] = i;
    }
}
 
bool solve() {
    while(!st.empty()) st.pop();
    for(int i = 1; i <= 2*(p+M); i ++) {
        v[i].clear();
        if(!dfn[i]) tarjan(i);
    }
    //printf("-----------%d
    ", scc);    
    for(int i = 1; i <= p; i ++) {
        if(belong[i] == belong[i+p]) return 0;
        pos[belong[i]] = belong[i+p];
        pos[belong[i+p]] = belong[i];
    }
    for(int i = p*2+1; i <= p*2+M; i ++) {
        if(belong[i] == belong[i+M]) return 0;
        pos[belong[i]] = belong[i+M];
        pos[belong[i+M]] = belong[i];
    }
    for(int i = 1; i <= p*2+M*2; i ++) {
        for(int j = head[i]; ~j; j = e[j].nxt) {
            int en = e[j].to;
            if(belong[i] != belong[en]) {
                du[belong[i]] ++;
                v[belong[en]].pb(belong[i]);
            }
        }
    }
    topo();
    return 1;
}
 
void init() {
    mem1(head);
    cnt = scc = 0;
    idx = 1;
    mem0(dfn); mem0(low); mem0(instack); mem0(belong);
    mem0(pos); mem0(du); mem0(output);
}
 
int l[400010], r[400010];
 
int main() {
    int x, y;
    while(~scanf("%d%d%d%d", &n, &p, &M, &m)) {
        init();
        for(int i = 0; i < n; i ++) {
            scanf("%d%d", &x, &y);
            add(x+p, y), add(y+p, x);
        }
        int id = p*2;
        for(int i = 1; i <= M; i ++) {
            if(i > 1) add(id+i, id+i-1);
            if(i < M) add(id+i+M, id+i+M+1);
        }
        for(int i = 1; i <= p; i ++) {
            scanf("%d%d", &x, &y);
            l[i] = x, r[i] = y;
            add(i, id+x);
            add(id+x+M, i+p);
            add(i, id+y+M+1);
            add(id+y+1, i+p);
        }
        for(int i = 0; i < m; i ++) {
            scanf("%d%d", &x, &y);
            add(x, y+p), add(y, x+p);
        }
        if(solve()) {
            int L = 0;
            for(int i = 0; i < out; i ++) {
                L = max(L, l[output[i]]);
            }
            printf("%d %d
    "    , out, L);
            for(int i = 0; i < out; i ++) {
                printf("%d ", output[i]);
            }
            printf("
    "    );
        }else printf("-1
    "    );
    }
    return 0;
}

    J-Monocarp and T-Shirts(期待+反発)
    よく知られているように、ACMを打つと服を出すことができます.あなたはn試合があります.試合ごとにPの確率でx-1の大きさの服を手に入れます.Qの確率でx+1の大きさの服を手に入れます.だから、1-P-Qの確率でxの大きさの服を手に入れます.同時に、n人の友达がn枚の大きさの異なる服を手に入れたいと思っています.友达の数の期待を満たすことができます.
    解題構想:友人の個数の期待を満たす=友人ごとに満たされる確率の和であるため,友人ごとに満たされる確率を求めればよい.確率を計算するときは反発すればよい(0.8 0.8 0.8の確率でx xを満たすと同時に0.7 0.7の確率でx x xを満たす.2つの確率は異なるイベントであるため、p(x)=0.8+0.7−0.8∗0.7 p(x)=0.8+0.7*0.7 p(x)=0.8+0.7−0.8∗0.7 p(x)=0.8+0.7−0.8*0.7 p(x)=0.8+0.7−0.8∗0.7)
    AC_code: 
    #include
 
#pragma GCC optimize(2)
#define bug printf("*********
    ");    
#define mem0(a) memset(a, 0, sizeof(a));
#define mem1(a) memset(a, -1, sizeof(a));
#define finf(a, n) fill(a, a+n, INF);
#define lowbit(x) x&-x
#define fuck(x) cout<
#define ios ios::sync_with_stdio(false);
#define pb(x) push_back(x)
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<LL, pair<int, LL> > LLppar;
typedef pair<int, int> par;
typedef pair<LL, int> LLpar;
const LL mod = 998244353;
const int inf = 1e9 + 7;
const LL INF = 1e18 + 7;
const int base = 131; //19260817 233 1331 1e9+7
const double eps = 0.000001;
 
int n;
LL p, q;
int a [200010];
 
LL ksm(LL a, int b) {
    LL ans = 1;
    while(b) {
        if(b&1) ans = ans*a%mod;
        a = a*a%mod;
        b /= 2;
    }
    return ans;
}
 
int main() {
    while(~scanf("%d%lld%lld", &n, &p, &q)) {
        for(int i = 0; i < n; i ++) {
            scanf("%d", &a[i]);
        }
        sort(a, a+n);
        LL r = (1000000LL-p-q)*ksm(1000000, mod-2)%mod;
        p = p*ksm(1000000, mod-2)%mod;
        q = q*ksm(1000000, mod-2)%mod;
        LL sum = 0;
        for(int i = 0; i < n; i ++) {
            int left = 0, right = 0;
            if(i > 0 && a[i-1]+1 == a[i]) left = 1;
            if(i < n-1 && a[i+1]-1 == a[i]) right = 1;
            sum += r;
            if(left) sum += q - r*q;
            if(right) sum += p - r*p;
            if(left && right) sum += r*p%mod*q%mod - p*q;
            sum = (sum%mod+mod)%mod;
        }
        printf("%lld
    "    , sum);
    }
    return 0;
}

    K-Moonbound(アナログ)
    最后にi行目j列を(i+j)%2==0 stand:stoneにして、11の充填を1つ选ぶことができて、2*2の充填を选ぶことができて、ある位置はそれを満たすことができて、后者は隣接してすでに充填されています.
    問題を解く構想:シミュレーションすればよい
    AC_code: 
    #include
const int inf = 1e9+7;
using namespace std;
 
int n;
 
int main() {
    while(~scanf("%d", &n)) {
        int k = 3*n*n/4;
        printf("%d
    "    , k);
        for(int i = n-1; i >= 1; i -= 2) {
            for(int j = 1; j <= n; j ++) {
                if((i+j)%2 == 0) {
                    printf("1 %d %d 1
    "    , i, j);
                    printf("1 %d %d 1
    "    , i+1, j+1);
                    printf("2 %d %d 2
    "    , i, j);
                }
            }
        }
    }
    return 0;
}

    L-Printer(暴力)
    2阶建てのビルがあって、上に下りてk k k时间を必要として、毎阶の隣の位置の移动は1 1 1时间を使って、ある位置からすべての1 1 1 1位置の时间の最大値の最小値と最大値を求めます.
    問題解決の考え方:暴力
    AC_code: 
    #include
const int inf = 1e9+7;
using namespace std;
 
int n, k;
char s1[1010], s2[1010];
 
int main() {
    while(~scanf("%d%d", &n, &k)) {
        scanf("%s%s", s1, s2);
        int ans = inf, idx1, idx2;
        for(int i = 0; i < n; i ++) {
            int sum1 = 0, sum2 = 0;
            for(int j = 0; j < n; j ++) {
                if(s1[j] == '1') sum1 = max(sum1, abs(j-i)), sum2 = max(sum2, i+j+1+1+k);
            }
            for(int j = 0; j < n; j ++) {
                if(s2[j] == '1') sum2 = max(sum2, abs(j-i)), sum1 = max(sum1, i+j+1+1+k);
            }
            if(sum1 < ans) {
                idx1 = 2, idx2 = i+1;
                ans = sum1;
            }
            if(sum2 < ans) {
                idx1 = 1, idx2 = i+1;
                ans = sum2;
            }
        }
        printf("%d
    %d %d
    "    , ans, idx1, idx2);
    }
    return 0;
}
    aidl
    潜移黙化学会WPF(テクニック編)--Items要素を持つコントロールサブアイテム取得(一)