Codeforces Round #277(Div. 2)_html/css_WEB-ITnose

Question A: http://codeforces.com/contest/486/problem/A

Analysis: After analyzing the odd and even numbers, the result will come out

Code:

#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;            }        }}

Question B: http://codeforces.com/contest/486/problem/B

Analysis: The question is that there is a 01 matrix A, Then the matrix B can be obtained based on A. The rule is Bij=1 if there is at least one 1 in row i or column j, otherwise Bij is 0. Now that the B matrix is ​​known, I want to ask if I can find a suitable A matrix.

It can be seen that if the B matrix element is 0, then the row and column of the element in the A matrix must also be all 0, so you can set all A to 1 at the beginning, and then set B The corresponding rows and columns that are 0 in A are set to 0, and finally the obtained A is used to find B to see if they are consistent. If not, NO

code is returned:

#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;                    }        }}

Question c: http://codeforces.com/contest/486/problem/C

Analysis: The meaning of the question is to ask how many steps it takes to make a given character To program a palindrome string, first of all, you can be sure that the pointer only needs to move in half of the string. For example, for a string with a length of 8, the current position is 3, then the string only needs to be at position 1234 at most. Just change the place, because the left part is equivalent to changing the right part, but the number of steps to move the pointer to the left when changing it to the right will be more. Secondly, if you switch to the current pointer to the left, it will still To judge whether the pointer is left first then right or first right then left, there are two different results. At the same time, you should pay attention to where the leftmost and rightmost need to go. For example, the 1st position and the 8th position are the same, then the most Just go to the second position left. . . The code written during the competition was quite messy. . .

Code:

#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;}

Question D: http://codeforces.com/contest/486/problem/D

Didn't do it during the game. . . Because it’s too late and my roommate needs to go to bed== After reading the question today, I can be sure that it is a tree DP. Generally, tree DP uses dp[i] to represent the number obtained with i as the root node. . .

Referring to other people's code, here we use dfs(i) to return how many qualified subtrees there are when i is the node and the weight of the i node is the largest. In this case, we only need to traverse Each node, and then treat each node as a root vertex, just calculate how many qualified subtrees there are. It should be noted that there may be repeated characters here, so you need to use visited[i] to determine whether i is the root. And whether the subtree with the maximum weight[i] has been processed

Code:

#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;}