Codeforces ラウンド #277(ディビジョン 2)_html/css_WEB-ITnose

質問 A: http://codeforces.com/contest/486/problem/A

分析: 奇数と偶数を分析した後、結果が出ます

コード:

#include <vector>#include <list>#include <map>#include <set>#include <deque>#include <stack>#include <bitset>#include <algorithm>#include <functional>#include <numeric>#include <utility>#include <sstream>#include <iostream>#include <iomanip>#include <cstdio>#include <cmath>#include <cstdlib>#include <ctime>#include <string.h>using namespace std;typedef long long ll;const int N=100010;ll arr[N];ll dp[110][2];ll n,m;int main(){        while(cin>>n)        {            if(n&1)            {                cout<<n*-1+n/2<<endl;            }            else            {                cout<<n/2<<endl;            }        }}

質問 B: http ://codeforces.com /contest/486/problem/B

分析: 問題は、01 の行列 A があり、行列 A に基づいて行列 B を取得できるということです。ルールは、ある場合 Bij=1 です。行 i または列 j に少なくとも 1 つの 1、それ以外の場合 Bij は 0 です。 B 行列がわかったので、適切な A 行列を見つけることができるかどうかを尋ねます。

行列 B の要素が 0 の場合、行列 A の要素の行と列もすべて 0 でなければならないことがわかります。そのため、最初にすべての A を 1 に設定し、その後すべての A を設定できます。 B の要素を 0 に変換し、A の対応する行と列を 0 に設定し、最後に取得した A を使用して B が一致しているかどうかを確認します。

コード:

#include <vector>#include <list>#include <map>#include <set>#include <deque>#include <stack>#include <bitset>#include <algorithm>#include <functional>#include <numeric>#include <utility>#include <sstream>#include <iostream>#include <iomanip>#include <cstdio>#include <cmath>#include <cstdlib>#include <ctime>#include <string.h>using namespace std;typedef long long ll;const int N=100010;int a[110][110];int b[110][110];int c[110][110];ll n,m;int main(){        while(cin>>n>>m)        {            for(int i=0;i<n;i++)                for(int j=0;j<m;j++)                {                    cin>>a[i][j];                    b[i][j]=1;                }            for(int i=0;i<n;i++)                for(int j=0;j<m;j++)                {                    if(a[i][j]==0)                    {                        for(int k=0;k<n;k++)                            b[k][j]=0;                        for(int k=0;k<m;k++)                            b[i][k]=0;                    }                }                memset(c,0,sizeof(c));                for(int i=0;i<n;i++)                    for(int j=0;j<m;j++)                    {                        for(int k=0;k<n;k++)                            c[i][j]|=b[k][j];                        for(int k=0;k<m;k++)                            c[i][j]|=b[i][k];                    }                    bool flag = true;                    for(int i=0;i<n;i++)                        for(int j=0;j<m;j++)                        {                            if(a[i][j]!=c[i][j])                                flag = false;                        }                    if(flag)                    {                        cout<<"YES"<<endl;                        for(int i=0;i<n;i++)                        {                            for(int j=0;j<m;j++)                                cout<<b[i][j]<<" ";                            cout<<endl;                        }                    }                    else                    {                        cout<<"NO"<<endl;                    }        }}

質問。 c: http://codeforces.com/contest/486/problem/C

分析: 問題は、与えられた文字列プログラムを回文文字列にするのに何ステップかかるかを尋ねることです。たとえば、長さが 8 の文字列の場合、ポインタは文字列の半分だけを移動する必要があります。現在の位置は 3 です。その場合、文字列は最大でも位置 1234 だけを変更する必要があります。これは、左側の部分と右側の部分が同じであるためです。は同等ですが、過去のポインタは にあります。 ただし、左側を変更するにはさらに多くの手順が必要になります。次に、左側の現在のポインタに切り替える場合、ポインタが最初に左にあるのか、次に右にあるのか、最初に右にあるのかを判断する必要があります。次に左に移動します。同時に 2 つの異なる結果に注意する必要があります。たとえば、1 番目の位置と 8 番目の位置が同じである場合は、最も左の位置のみに注意する必要があります。 2番目の位置に移動します。 。 。コンテスト中に書かれたコードは非常に厄介でした。 。 。

コード:

#include <vector>#include <list>#include <map>#include <set>#include <deque>#include <stack>#include <bitset>#include <algorithm>#include <functional>#include <numeric>#include <utility>#include <sstream>#include <iostream>#include <iomanip>#include <cstdio>#include <cmath>#include <cstdlib>#include <ctime>#include <string.h>using namespace std;typedef long long ll;const int N=100010;int a[110][110];int b[110][110];int c[110][110];int n,m;int main(){        while(cin>>n>>m)        {            string s;            cin>>s;            m = min(m,n+1-m);            m--;            int ret = 0;            int start = 0;            while(start<n-1-start&&s[start]==s[n-1-start])                start++;            if(start>=n-1-start)            {                cout<<0<<endl;                continue;            }            ret+=abs(m-start);            int last = start;            while(start<n-1-start)            {                int t1 = s[start]-'a';                int t2 = s[n-1-start]-'a';                int diff = max(t1,t2)-min(t1,t2);                int t = min(diff,26-diff);                if(t!=0)                {                    ret+=t;                    ret+=abs(start-last);                    last = start;                }                start++;            }            int ret1 = 0;            int start1 = n%2==0?n/2-1:n/2;            while(start1>=0&&s[start1]==s[n-1-start1])                start1--;            if(start1<0)            {                cout<<0<<endl;                continue;            }            ret1+=abs(m-start1);            int last1 = start1;            while(start1>=0)            {                int t1 = s[start1]-'a';                int t2 = s[n-1-start1]-'a';                int diff = max(t1,t2)-min(t1,t2);                int t = min(diff,26-diff);                if(t!=0)                {                    ret1+=t;                    ret1+=abs(start1-last1);                    last1 = start1;                }                start1--;            }            ret = min(ret,ret1);            cout<<ret<<endl;        }        return 0;}

質問 D: http://codeforces.com/contest/486/problem/D

コンテストでは実行されませんでした。 。 。なぜなら、もう遅すぎるし、ルームメイトは寝る必要があるからです== 今日の質問を読んだ後、それがツリー DP であることを確信できます。 一般に、ツリー DP は i をルートとして得られる数を表すために dp[i] を使用します。ノード。 。 。

他の人のコードを参照すると、ここでは dfs(i) を使用して、i がノードであり、i ノードの重みが最大である場合に、修飾されたサブツリーの数を返します。この場合、各ノードを走査するだけで済みます。次に、各ノードをルート頂点として扱い、修飾されたサブツリーがいくつあるかを計算します。ここで文字が繰り返される可能性があるため、i がルートであり、最大重みが であるかどうかを判断するために Visited[i] を使用する必要があることに注意してください。 [i] のサブツリーが処理されているかどうか

コード:

#include <iostream>#include <algorithm>#include <string>#include <map>#include <vector>#include <cstring>#include <string.h>#include <cstdio>#include <stack>#include <iomanip>#include <math.h>using namespace std;typedef long long ll;const int mod = 1e9+7;const int N=3010;ll x,y,m,n,k;pair<ll,ll>  arr[N];bool deleted[N];string s;int a,b,c,d;vector<int> v[N];bool visited[N];int weight[N];ll dfs(int cur,int par,int up,int down){    if(weight[cur]<down||weight[cur]>up)        return 0;    if(weight[cur]==up&&!visited[cur])        return 0;    ll ans = 1;    for(int i=0;i<v[cur].size();i++)    {        int next = v[cur][i];        if(next==par)continue;        ans = (ans*(dfs(next,cur,up,down)+1))%mod;    }    return ans;}int main(){    while(cin>>d>>n)    {                for(int i=1;i<=n;i++)        {            cin>>weight[i];            v[i].clear();            visited[i]=true;        }        for(int i=0;i<n-1;i++)        {            int a,b;            cin>>a>>b;            v[a].push_back(b);            v[b].push_back(a);        }        ll ans = 0;        for(int i=1;i<=n;i++)        {            ans = (ans+dfs(i,-1,weight[i],weight[i]-d))%mod;            visited[i]=false;        }        cout<<ans<<endl;    }    return 0;}