Codeforces Round#656(Div.3)ABCDE問題解(再帰二分、トポロジー)

55138 ワード
codeforces アルゴリズム
A. Three Pairwise Maximums
タイトルリンク
https://codeforces.com/contest/1385/problem/A
構想
a,b,cを非減算ソートした後、x=b,y=z=c yがzに等しくなければ解がなく、そうでなければa=1,b=x,c=yが1組の解である
コード#コード#
#include
#include
#include
using namespace std;
const double pi = acos(-1.0);
#define INF 0x7f7f7f
// #define TDS_ACM_LOCAL
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int t;
    cin>>t;
    while(t--){
        int x, y, z;
        cin>>x>>y>>z;
        if(x>y) swap(x,y);
        if(x>z) swap(x,z);
        if(y>z) swap(y,z);
        if(y==z)
        {
            cout<<"YES"<<endl;
            cout<<"1 "<<x<<" "<<y<<endl;
        }   
        else
            cout<<"NO"<<endl;
    }
    return 0;
}

B. Restore the Permutation by Merger
タイトルリンク
https://codeforces.com/contest/1385/problem/B
構想
2回目に同じものに出会ったら出力する
コード#コード#
#include
#include
#include
using namespace std;
const double pi = acos(-1.0);
#define INF 0x7f7f7f
// #define TDS_ACM_LOCAL
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int t;
    cin>>t;
    while(t--){
        int n, a, p[55]={0};
        cin>>n;
        for(int i=0; i<2*n; i++){
            cin>>a;
            p[a]++;
            if(p[a]==2)
                cout<<a<<" ";
        }
        cout<<endl;
    }
    return 0;
}

C.Make It Good(ピークピークの底を逆方向に求める)
タイトルリンク
https://codeforces.com/contest/1385/problem/C
構想
テーマの要求を満たすのはとても明らかです1、全過程は変わらない2、全過程は非漸減あるいは非漸増3、1つの極大値の峰頂解を持っています:右から左まで峰頂を捜索します(>=)、更に峰頂から左へ峰底を捜索します(<=)
コード#コード#
#include
#include
#include
#include
#include
using namespace std;
const double pi = acos(-1.0);
#define INF 0x7f7f7f
// #define TDS_ACM_LOCAL
#define mem(a,b) memset(a , b , sizeof(a))
#define FOR(i, x, n) for(int i = x;i <= n; i++)
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int t;
    cin>>t;
    while(t--){
        int n, a[200009]={0};
        cin>>n;
        for(int i=0; i<n; i++)
            cin>>a[i];
        int k=n-1;
        while(a[k-1]>=a[k]&&k>=1)
            k--;
        while(a[k-1]<=a[k]&&k>=1)
            k--;
        cout<<k<<endl;
    }
    return 0;
}

D.a-Good String(二分、再帰)
タイトルリンク
https://codeforces.com/contest/1385/problem/D
構想
n=2^kであるため、nは2の倍数であり、1文字のみが再帰二分の方法を用いて、現在のサブストリングの左と右がcになるために必要な操作回数をそれぞれ計算し、様々な場合の回数を最小化すればよい
コード#コード#
#include
#include
#include
#include
#include
using namespace std;
const double pi = acos(-1.0);
#define INF 0x7f7f7f
// #define TDS_ACM_LOCAL
#define mem(a,b) memset(a , b , sizeof(a))
#define FOR(i, x, n) for(int i = x;i <= n; i++)

inline void read(int &x) {
	char ch = getchar(); int f = 1; x = 0;
	while (!isdigit(ch) && ch^'-') ch = getchar();
	if (ch == '-') f = -1, ch = getchar();
	while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
	x *= f;
}

char s[131080];
int t, n, ans;

int solve(int l, int r, char c){                                         //  c  abcd...  
    if(l==r)    return s[l]==c? 0:1;                                     //            0，  1
    int mid=(l+r)>>1, left=0, right=0;                                   //                     
    FOR(i, l, mid)  left+=(s[i]==c? 0:1);                                //              
    FOR(i, mid+1, r)    right+=(s[i]==c? 0:1);
    return min(left+solve(mid+1, r, c+1), right+solve(l, mid, c+1));     //              
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    read(t);
    while (t--)
    {
       read(n);
       scanf("%s", s+1);
       ans=solve(1, n, 'a');
       cout<<ans<<endl;
    }
    return 0;
}

E. Directing Edges
タイトルリンク>
https://codeforces.com/contest/1385/problem/E
構想
テーマの要求が無環なので、だからtoposortを使って(トポロジーソート)既知の有向辺計算入度でトポロジーソート検出を行うすべての点がトポロジーシーケンスにあるか否かを示し、残りの点は有環が先に除去された点が前に並び、後に除去された点が後ろに並んでいるため、前から後にエッジを追加してもトポロジーシーケンスに影響を及ぼさないので無向辺を有向辺にする場合は前の点から後ろの点がつながっていればいい
コード#コード#
#include
#include
#include
#include
#include
using namespace std;
#define pb push_back
#define mp make_pair
#define X first
#define Y second
const int N=200009;
// #define TDS_ACM_LOCAL

int tx, n, m, a[N], in_degree[N];
int t, x, y;
vector<pair<int,int>> ma[N];
vector<int>topo;

inline void read(int &x) {
	char ch = getchar(); int f = 1; x = 0;
	while (!isdigit(ch) && ch^'-') ch = getchar();
	if (ch == '-') f = -1, ch = getchar();
	while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
	x *= f;
}

void toposort(){
    topo.clear();                                //       
    queue<int>q;                                 //     
    for(int i=1; i<=n; i++)                      //    0       
        if(!in_degree[i])
            q.push(i);
    while(q.size()){
        x=q.front();
        q.pop();
        topo.pb(x);                             //         
        for(int i=0; i<ma[x].size(); i++){      //              （         1
            y=ma[x][i].X, t=ma[x][i].Y;
            if(t){
                if(!--in_degree[y])
                    q.push(y);
            }
        }
    }
}

void solve(){
    read(n), read(m);
    for(int i=1; i<=n; i++) {        //           
        in_degree[i]=0;
        ma[i].clear();
    }
    while(m--){
        read(t), read(x), read(y);
        if(t){                       //    ，  x->y，        ，     1
            ma[x].pb(mp(y,t));
            in_degree[y]++;
        } 
        else{                        //    ，  x->y,y->x，        
            ma[x].pb(mp(y,t));
            ma[y].pb(mp(x,t));
        }
    }
    toposort();
    if(topo.size()!=n){              //           ，    
        cout<<"NO"<<endl;
        return ;
    }
    else{
        cout<<"YES"<<endl;
        for(int i=0; i<n; i++)       //             
            a[topo[i]]=i;
        for(int i=1; i<=n; i++){
            for(int j=0; j<ma[i].size(); j++){        //      
                y=ma[i][j].X, t=ma[i][j].Y;
                if(t)                                 //       
                    cout<<i<<" "<<y<<endl;
                else{                                 //                   
                    if(a[i]<a[y])
                        cout<<i<<" "<<y<<endl;
                }
            }
        }
    }
    
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    read(tx);
    while (tx--) solve();
    return 0;
}
rubyとpythonの基本的なやつ対応表メモ
An error occurred while installing mysql2 (0.4.10)