Codeforces Round #496 (Div. 3) C D E1 E2 F

128521 ワード
Codeforces補題
Codeforces Round #496 (Div. 3)
Problem A
題意:考え方:

Problem B
題意:考え方:

Problem C
題意:n個の数を与えて、最低数の数を削除して残りの各数がいつも対応する別の数を見つけることができるようにする2個の数の和は2 x 2^x 2 x(xは非負の整数)の構想を尋ねる:各数が2 0 2^0 20~2*1 e 9より小さい最大の2 x 2^x 2 xを形成するのに必要な別の数を列挙して、現在の数が存在する限りOKである.もちろん自分が2 x 2^x 2 xであることを排除して、見つけた残りの半分も2 x 2^x 2 xであり、自分の場合です.
#include

using namespace std;

#define ll long long
#define for1(i,a,b) for (int i=(a);i<=(b);i++)
#define for0(i,a,b) for (int i=(a);i
#define rof1(i,a,b) for (int i=(a);i>=(b);i--)
#define rof0(i,a,b) for (int i=(a);i>(b);i--)
#define fi first
#define se second
#define pb push_back
#define duozu int __T;scanf("%d",&__T);for1(ica,1,__T)
void _r(const int&x){scanf("%d",&x);}
void _r(const ll&x){scanf("%I64d",&x);}
void _r(const char*x){scanf("%s",x);}
void R(){}
template<class T,class... U>void R(const T&head,const U&...tail){_r(head);R(tail...);}
void _w(const char x){putchar(x);}
void _w(const char*x){printf("%s",x);}
void _w(const int x){printf("%d",x);}
void _w(const ll x){printf("%I64d",x);}
void _w(const double x){printf("%.6f",x);}
void W(){}
template<class T,class...U>void W(const T&head,const U&...tail){_w(head);putchar(sizeof...(tail)?' ':'
');W(tail...);}
const ll mod = 1e9+7;
ll fp1(ll a,ll b){ll ans=1;while (b){if(b&1)ans*=a;b>>=1;a*=a;}return ans;}
ll fp2(ll a,ll b){ll ans=1;while (b){if(b&1)ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans;}
ll Read(){
    ll res=0,flag=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if (ch=='-')flag = -1;ch = getchar();}
    while (ch>='0' && ch<='9'){res = res*10+ch-'0';ch = getchar();}
    return res*flag;
}

const int N = 12e4+5;

int a[N];
ll bina[50],idx;
unordered_map<int,int>mp;

void prework(){
    idx = 0;
    while ((1<<idx)<=1e9) {bina[idx] = 1<<idx;idx++;}
    bina[idx] = 1<<idx;
    idx++;
}

int main()
{
    int n;
    prework();
    //for0(i,0,idx) W(bina[i]);
    while (~scanf("%d",&n)){
        int ans = 0;
        mp.clear();

        for0(i,0,n){
            R(a[i]);
            mp.count(a[i])?mp[a[i]]++:mp[a[i]]=1;
        }

        for0(i,0,n){
            int j = 0;
            for (;j<idx;j++){
                int need = bina[j] - a[i];
                if (mp.count(need)){
                    if (need==a[i] && mp[need]>1) break;
                    else if (need != a[i]) break;
                }
            }
            if (j==idx) ans++;
        }
        
        W(ans);
    }
    return 0;
}

Problem D
标题:0~9のみの串を与え、生前ガイド0を産まずに任意に切断することができ、最大でどれだけ3で割り切れるかを尋ねる構想:まずすべての0369を単独で切除する.0369自体が3で割り切れるため、他の数はこれらの0とつながって1つの数を構成するよりも節約してもっと多くの数を集めることができるからだ.残りの数にはs[i]%3=1,s[i]%3=2の2種類がある.そのため、2つの数しか残っていません.1と2です.そこで今、私たちは12の列しか残っていないセグメントをたくさん手に入れました.どのように各セグメントを処理して、各セグメントが3で除かれる数をできるだけ多くしますか.明らかに私达は行ってから最も短いのを探して、构成することができる限りすぐに使う必要があります.どうしてこのように最も良いのでしょうか.もし今のグループができないのは后でグループを作るためにもっと多いに违いありません.それでは、今のグループの必ず后のものと使って、结果は数量が同じだけではなくて、残って提供した接尾辞はもとよりも短いです.では、どうやって使えばいいのでしょうか.まず少なくとも2つが必要で、仮に下付き文字が0から始まると(後に下付き文字でその数を指す)、私たちは1から0と1が逆かどうかを判断し、逆に直接3を構成して、それから2位を後ろに跳んで、3と2が逆かどうかを判断します.もし0と1が同じならば、私达は更に2を见て、もし同じならば、それではこの3位は使って、それから后ろに3位を跳びます次の位も使ってしまったので、2と1が异なって、それは慌てなくて、このように21が3の倍数を构成することができるため、明らかにこれは前の3位が最も速く3の倍数を构成する方法です.
#include

using namespace std;

#define ll long long
#define for1(i,a,b) for (int i=(a);i<=(b);i++)
#define for0(i,a,b) for (int i=(a);i
#define rof1(i,a,b) for (int i=(a);i>=(b);i--)
#define rof0(i,a,b) for (int i=(a);i>(b);i--)
#define fi first
#define se second
#define pb push_back
#define duozu int __T;scanf("%d",&__T);for1(ica,1,__T)
void _r(const int&x){scanf("%d",&x);}
void _r(const ll&x){scanf("%I64d",&x);}
void _r(const char*x){scanf("%s",x);}
void R(){}
template<class T,class... U>void R(const T&head,const U&...tail){_r(head);R(tail...);}
void _w(const char x){putchar(x);}
void _w(const char*x){printf("%s",x);}
void _w(const int x){printf("%d",x);}
void _w(const ll x){printf("%I64d",x);}
void _w(const double x){printf("%.6f",x);}
void W(){}
template<class T,class...U>void W(const T&head,const U&...tail){_w(head);putchar(sizeof...(tail)?' ':'
');W(tail...);}
const ll mod = 1e9+7;
ll fp1(ll a,ll b){ll ans=1;while (b){if(b&1)ans*=a;b>>=1;a*=a;}return ans;}
ll fp2(ll a,ll b){ll ans=1;while (b){if(b&1)ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans;}
ll Read(){
    ll res=0,flag=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if (ch=='-')flag = -1;ch = getchar();}
    while (ch>='0' && ch<='9'){res = res*10+ch-'0';ch = getchar();}
    return res*flag;
}

const int N = 2e5+5;

char s[N];
vector<int>a[N];

int main()
{
    while (~scanf("%s",s)){
        int idx = 0;
        int ans = 0;
        a[0].clear();
        for (int i=0;s[i];i++){
            int num = (s[i]-'0')%3;
            if (!num) {ans++;a[++idx].clear();}
            else a[idx].pb(num);
        }
        for1(i,0,idx){
            for0(j,1,a[i].size()){
                if (j+1<a[i].size() && a[i][j-1]==a[i][j] && a[i][j]==a[i][j+1]){
                    ans++;
                    j+=2;
                }
                else if (a[i][j]!=a[i][j-1]){
                    ans++;
                    j++;
                } 
            }
        }
        W(ans);
    }
    return 0;
}

Problem E1
問題:n個の数を与えて、1~nのこのn個の数のある種類の配列で、区間の並べ替えの後で中位数がmの区間の個数の構想を尋ねます:1回の配列を遍歴して、mの位置を探し当てて、そしてその他の数を処理します——m/より小さくてmが1/-1になります.mは左右に2段に分かれています.区間内でmの他の数の和を除いて0または1でmを中位数とすることができるように、mの位置から左右に延びて左右の境界を決定することに相当する.m右側のすべての可能な接頭辞と対応回数を前処理します.左の場合は右から左へ遍歴し,和を求め,右に対応して和が0/1の数が存在するかどうかを探し,複雑度O(N)が注意しなければならないのはmそのものも答えであり,区間が片方だけである場合である.
#include

using namespace std;

#define ll long long
#define for1(i,a,b) for (int i=(a);i<=(b);i++)
#define for0(i,a,b) for (int i=(a);i
#define rof1(i,a,b) for (int i=(a);i>=(b);i--)
#define rof0(i,a,b) for (int i=(a);i>(b);i--)
#define fi first
#define se second
#define pb push_back
#define duozu int __T;scanf("%d",&__T);for1(ica,1,__T)
void _r(const int&x){scanf("%d",&x);}
void _r(const ll&x){scanf("%I64d",&x);}
void _r(const char*x){scanf("%s",x);}
void R(){}
template<class T,class... U>void R(const T&head,const U&...tail){_r(head);R(tail...);}
void _w(const char x){putchar(x);}
void _w(const char*x){printf("%s",x);}
void _w(const int x){printf("%d",x);}
void _w(const ll x){printf("%I64d",x);}
void _w(const double x){printf("%.6f",x);}
void W(){}
template<class T,class...U>void W(const T&head,const U&...tail){_w(head);putchar(sizeof...(tail)?' ':'
');W(tail...);}
const ll mod = 1e9+7;
ll fp1(ll a,ll b){ll ans=1;while (b){if(b&1)ans*=a;b>>=1;a*=a;}return ans;}
ll fp2(ll a,ll b){ll ans=1;while (b){if(b&1)ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans;}
ll Read(){
    ll res=0,flag=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if (ch=='-')flag = -1;ch = getchar();}
    while (ch>='0' && ch<='9'){res = res*10+ch-'0';ch = getchar();}
    return res*flag;
}

const int N = 2e5+5;

map<int,int>mp;
vector<int>a,b;

int main()
{
    int n,m;
    while (~scanf("%d %d",&n,&m)){
        mp.clear();a.clear();b.clear();
        bool flag = false;

        for1(i,1,n){
            int x;
            R(x);
            if (x==m) flag = true;
            else flag?b.pb(x>m?1:-1) : a.pb(x>m?1:-1);
        }
        for (int i=a.size()-2;i>=0;i--) a[i] += a[i+1];
        for (int i=1;i<b.size();i++) b[i] += b[i-1];
        for (int i=0;i<b.size();i++) mp.count(b[i])==0?mp[b[i]]=1:mp[b[i]]++;
        ll ans = 1;
        if (mp.count(1)) ans += mp[1];
        if (mp.count(0)) ans += mp[0];
        for (int i=0;i<a.size();i++){
            if (a[i]==0||a[i]==1) ans++;
            if (mp.count(0-a[i])) ans += mp[0-a[i]];
            if (mp.count(1-a[i])) ans += mp[1-a[i]];
        }
        W(ans);
    }
    return 0;
}

Problem E2
題意:長さnの数列、質問区間中位数はmの区間の個数です.mは、m以上を求める個数比がmよりも小さい区間セグメント数をGC(m)と定義する複数の考え方があるかもしれない.そこで,問題をGC(m)−GC(m+1)に変換し,m以上の数を1,残りの−1,すなわち,区間を求めることと0以上の区間個数に相当する.2つの問題は等価で、そのうちの1つを言うだけで、具体的な方法は接頭辞を維持することであり、各接頭辞の出現回数を記録することであり、各接頭辞はこの接頭辞のどの接頭辞を削除するかを求めることで、結果>0、すなわち、接頭辞の中で現在の接頭辞と小さいものを求めることができ、動的に#include using namespace std; #define ll long long #define for1(i,a,b) for (int i=(a);i<=(b);i++) #define for0(i,a,b) for (int i=(a);i #define rof1(i,a,b) for (int i=(a);i>=(b);i--) #define rof0(i,a,b) for (int i=(a);i>(b);i--) #define fi first #define se second #define pb push_back #define duozu int __T;scanf("%d",&__T);for1(ica,1,__T) void _r(const int&x){scanf("%d",&x);} void _r(const ll&x){scanf("%I64d",&x);} void _r(const char*x){scanf("%s",x);} void R(){} template<class T,class... U>void R(const T&head,const U&...tail){_r(head);R(tail...);} void _w(const char x){putchar(x);} void _w(const char*x){printf("%s",x);} void _w(const int x){printf("%d",x);} void _w(const ll x){printf("%I64d",x);} void _w(const double x){printf("%.6f",x);} void W(){} template<class T,class...U>void W(const T&head,const U&...tail){_w(head);putchar(sizeof...(tail)?' ':'
');W(tail...);} const ll mod = 1e9+7; ll fp1(ll a,ll b){ll ans=1;while (b){if(b&1)ans*=a;b>>=1;a*=a;}return ans;} ll fp2(ll a,ll b){ll ans=1;while (b){if(b&1)ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans;} ll Read(){ ll res=0,flag=1;char ch=getchar(); while(ch<'0'||ch>'9'){if (ch=='-')flag = -1;ch = getchar();} while (ch>='0' && ch<='9'){res = res*10+ch-'0';ch = getchar();} return res*flag; } const int N = 2e5+5; unordered_map<int,int>mp; int a[N],n; ll GreatCount(int m){ ll res = 0,sum = 0,add = 0; mp.clear(); mp[0] = 1; for0(i,0,n){ if (a[i]>=m){ if (mp.count(sum)==1) add += mp[sum]; sum++; } else { sum--; if (mp.count(sum)==1) add -= mp[sum]; } mp.count(sum)==1?mp[sum]++:mp[sum] = 1; res += add; } return res; } int main() { int m; while (~scanf("%d %d",&n,&m)){ for0(i,0,n) R(a[i]); W(GreatCount(m)-GreatCount(m+1)); } return 0; }
Problem F
題意:n個の点mの辺の図を与えて、n個の点の連通を保証します.n-1エッジを選択してn点を接続し、すべてのポイントから1番ポイントまでの総距離と(各エッジ長さは1と表記)が最も近いようにします.k種類の選択案を見つける必要があります.総方法数がk種類未満であれば、すべての方法を見つけることができます.構想:まずどのように総距離と最近を考えてみて、すべての点ができるだけ早く1につながっていることで、私たちは1からBFSを行うことができて、すべての点が遍歴された層数は距離1の最も短い距離で、d[i]を覚えています.もし私たちが総距離の最小の異なる方法を探すならば、各点はその階で遍歴しなければなりません.したがって,異なる方法の本質は,最初にBFSによって形成された1層のノードでは,各層のノードは変わらないが,‘このノードは前の層の誰の息子であるか’を変えることである.したがって,iノードが選択可能であることを示す父親がそのエッジに対応する番号の集合をfa[i][]で維持し,これはd[]に基づいてすべてのエッジを遍歴すればよい.次にfaを並べてk種類の方法を組み合わせることに相当する.どのように重複しない列挙は終わりますか?公式の問題解のやり方はすごいと感じて、別の配列(下のコードでnt[i])を開いて対応するfa[]を記録して、現在何人目の父親に列挙しました.次に、次のノードは、父親を交換し、現在のすべてのビットが最後のビットを列挙した場合にのみ、左ビットが満たされ、右に1つ進むプロセスに相当します.例を挙げると、1321でシミュレーションします.1111121111311 11212121321です.
#include

using namespace std;

#define ll long long
#define for1(i,a,b) for (int i=(a);i<=(b);i++)
#define for0(i,a,b) for (int i=(a);i
#define rof1(i,a,b) for (int i=(a);i>=(b);i--)
#define rof0(i,a,b) for (int i=(a);i>(b);i--)
#define fi first
#define se second
#define pb push_back
#define duozu int __T;scanf("%d",&__T);for1(ica,1,__T)
void _r(const int&x){scanf("%d",&x);}
void _r(const ll&x){scanf("%I64d",&x);}
void _r(const char*x){scanf("%s",x);}
void R(){}
template<class T,class... U>void R(const T&head,const U&...tail){_r(head);R(tail...);}
void _w(const char x){putchar(x);}
void _w(const char*x){printf("%s",x);}
void _w(const int x){printf("%d",x);}
void _w(const ll x){printf("%I64d",x);}
void _w(const double x){printf("%.6f",x);}
void W(){}
template<class T,class...U>void W(const T&head,const U&...tail){_w(head);putchar(sizeof...(tail)?' ':'
');W(tail...);}
const ll mod = 1e9+7;
ll fp1(ll a,ll b){ll ans=1;while (b){if(b&1)ans*=a;b>>=1;a*=a;}return ans;}
ll fp2(ll a,ll b){ll ans=1;while (b){if(b&1)ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans;}
ll Read(){
    ll res=0,flag=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if (ch=='-')flag = -1;ch = getchar();}
    while (ch>='0' && ch<='9'){res = res*10+ch-'0';ch = getchar();}
    return res*flag;
}

const int N = 2e5+5;

int a[N],b[N];
vector<int>fa[N],g[N];
vector<string>res;
int nt[N],d[N];
queue<int>que;

int main()
{
    int n,m,k;
    R(n,m,k);
    for1(i,1,m){
        R(a[i],b[i]);
        a[i]--,b[i]--;
        g[a[i]].pb(b[i]);
        g[b[i]].pb(a[i]);
    }
    que.push(0);
    d[0] = 1;
    while (!que.empty()){
        int u = que.front();
        que.pop();
        for (auto v:g[u]){
            if (!d[v]){
                d[v] = d[u]+1;
                que.push(v);
            }
        }
    }

    for1(i,1,m){
        int u = a[i],v = b[i];
        if (d[u]+1==d[v]) fa[v].pb(i);
        if (d[v]+1==d[u]) fa[u].pb(i);
    }

    for1(i,1,k){
        string s(m,'0');
        for1(i,1,n-1){
            s[fa[i][nt[i]]-1] = '1';//      0      1    -1
        }
        res.pb(s);
        bool ok = false;
        for1(i,1,n-1){
            if (nt[i]+1<fa[i].size()){
                nt[i]++;
                ok = true;
                break;
            }
            else nt[i] = 0;
        }
        if (!ok) break;
    }

    cout << res.size() << endl;
    for (auto s:res) cout << s << endl;

    return 0;
}
PHP操作mysqlクラスのパッケージ
Laravelから受け取ったデータをVueで非同期で更新する。