轉載請注明出處：?http://www.cnblogs.com/fraud/?????????? ——by fraud

A. Calculating Function

水題，判個奇偶即可

1 #include <iostream> 2 #include <sstream> 3 #include <ios> 4 #include <iomanip> 5 #include <functional> 6 #include <algorithm> 7 #include <vector> 8 #include <string> 9 #include <list> 10 #include <queue> 11 #include <deque> 12 #include <stack> 13 #include <set> 14 #include <map> 15 #include <cstdio> 16 #include <cstdlib> 17 #include <cmath> 18 #include <cstring> 19 #include <climits> 20 #include <cctype> 21 using namespace std; 22 #define XINF INT_MAX 23 #define INF 0x3FFFFFFF 24 #define MP(X,Y) make_pair(X,Y) 25 #define PB(X) push_back(X) 26 #define REP(X,N) for(int X=0;X<N;X++) 27 #define REP2(X,L,R) for(int X=L;X<=R;X++) 28 #define DEP(X,R,L) for(int X=R;X>=L;X--) 29 #define CLR(A,X) memset(A,X,sizeof(A)) 30 #define IT iterator 31 typedef long long ll; 32 typedef pair<int,int> PII; 33 typedef vector<PII> VII; 34 typedef vector<int> VI; 35 36 int main() 37 { 38 ios::sync_with_stdio(false); 39 ll n; 40 while(cin>>n) 41 { 42 if(n&1)cout<<-(n+1)/2<<endl; 43 else cout<<n/2<<endl; 44 } 45 return 0; 46 } View Code

B. OR in Matrix

先把A全部初始化為1，再把B中為0的對應的行和列在A中設為0，最后再通過得到的A來求B，看是否一致

1 #include <iostream> 2 #include <sstream> 3 #include <ios> 4 #include <iomanip> 5 #include <functional> 6 #include <algorithm> 7 #include <vector> 8 #include <string> 9 #include <list> 10 #include <queue> 11 #include <deque> 12 #include <stack> 13 #include <set> 14 #include <map> 15 #include <cstdio> 16 #include <cstdlib> 17 #include <cmath> 18 #include <cstring> 19 #include <climits> 20 #include <cctype> 21 using namespace std; 22 #define XINF INT_MAX 23 #define INF 0x3FFFFFFF 24 #define MP(X,Y) make_pair(X,Y) 25 #define PB(X) push_back(X) 26 #define REP(X,N) for(int X=0;X<N;X++) 27 #define REP2(X,L,R) for(int X=L;X<=R;X++) 28 #define DEP(X,R,L) for(int X=R;X>=L;X--) 29 #define CLR(A,X) memset(A,X,sizeof(A)) 30 #define IT iterator 31 typedef long long ll; 32 typedef pair<int,int> PII; 33 typedef vector<PII> VII; 34 typedef vector<int> VI; 35 int a[2010]; 36 vector<int>G[2010]; 37 int d,n; 38 const ll MOD=1000000007; 39 ll dp[2010]; 40 void dfs(int v,int u,int root,int x) 41 { 42 if((a[v]<x&&x-a[v]<=d)||(a[v]==x&&root>=v)) 43 { 44 //cout<<v<<" "; 45 dp[v]=1; 46 for(int i=0;i<G[v].size();i++) 47 { 48 if(G[v][i]==u)continue; 49 dfs(G[v][i],v,root,x); 50 dp[v]*=(dp[G[v][i]]+1); 51 dp[v]%=MOD; 52 } 53 54 } 55 return ; 56 } 57 int main() 58 { 59 ios::sync_with_stdio(false); 60 //freopen("in.in","r",stdin); 61 while(cin>>d>>n) 62 { 63 for(int i=0;i<n;i++) 64 { 65 cin>>a[i]; 66 G[i].clear(); 67 } 68 int u,v; 69 for(int i=0;i<n-1;i++) 70 { 71 cin>>u>>v; 72 u--,v--; 73 G[u].PB(v); 74 G[v].PB(u); 75 } 76 ll ans=0; 77 for(int i=0;i<n;i++) 78 { 79 CLR(dp,0); 80 dfs(i,i,i,a[i]); 81 ans+=dp[i]; 82 ans%=MOD; 83 } 84 cout<<ans<<endl; 85 86 } 87 return 0; 88 } View Code

C. Palindrome Transformation

貪心，只需要看初始位置所在的一半字符串。取短的那一部分先改。

1 #include <iostream> 2 #include <sstream> 3 #include <ios> 4 #include <iomanip> 5 #include <functional> 6 #include <algorithm> 7 #include <vector> 8 #include <string> 9 #include <list> 10 #include <queue> 11 #include <deque> 12 #include <stack> 13 #include <set> 14 #include <map> 15 #include <cstdio> 16 #include <cstdlib> 17 #include <cmath> 18 #include <cstring> 19 #include <climits> 20 #include <cctype> 21 using namespace std; 22 #define XINF INT_MAX 23 #define INF 0x3FFFFFFF 24 #define MP(X,Y) make_pair(X,Y) 25 #define PB(X) push_back(X) 26 #define REP(X,N) for(int X=0;X<N;X++) 27 #define REP2(X,L,R) for(int X=L;X<=R;X++) 28 #define DEP(X,R,L) for(int X=R;X>=L;X--) 29 #define CLR(A,X) memset(A,X,sizeof(A)) 30 #define IT iterator 31 typedef long long ll; 32 typedef pair<int,int> PII; 33 typedef vector<PII> VII; 34 typedef vector<int> VI; 35 string s; 36 int main() 37 { 38 ios::sync_with_stdio(false); 39 int n,p; 40 cin>>n>>p>>s; 41 int len=n; 42 int ans=0; 43 int x=(n+1)/2; 44 if(p<=x) 45 { 46 p--; 47 int lx=0,rx=0; 48 int i=0; 49 while(s[i]==s[len-1-i]&&i<p)i++; 50 ans+=p-i; 51 lx=p-i; 52 int temp; 53 while(i<=p) 54 { 55 if(s[i]!=s[len-1-i]) 56 { 57 temp=max(s[i],s[len-1-i])-min(s[i],s[len-1-i]); 58 ans+=min(temp,26-temp); 59 } 60 i++; 61 } 62 i=x-1; 63 while(s[i]==s[len-1-i]&&i>p)i--; 64 rx=i-p; 65 ans+=i-p; 66 while(i>p) 67 { 68 if(s[i]!=s[len-1-i]) 69 { 70 temp=max(s[i],s[len-1-i])-min(s[i],s[len-1-i]); 71 ans+=min(temp,26-temp); 72 } 73 i--; 74 } 75 ans+=min(lx,rx); 76 77 } 78 else 79 { 80 p--; 81 int lx=0,rx=0; 82 int i=x; 83 while(s[i]==s[len-1-i]&&i<p)i++; 84 ans+=p-i; 85 lx=p-i; 86 int temp; 87 while(i<=p) 88 { 89 if(s[i]!=s[len-1-i]) 90 { 91 temp=max(s[i],s[len-1-i])-min(s[i],s[len-1-i]); 92 ans+=min(temp,26-temp); 93 } 94 i++; 95 } 96 i=len-1; 97 while(s[i]==s[len-1-i]&&i>p)i--; 98 rx=i-p; 99 ans+=i-p; 100 while(i>p) 101 { 102 if(s[i]!=s[len-1-i]) 103 { 104 temp=max(s[i],s[len-1-i])-min(s[i],s[len-1-i]); 105 ans+=min(temp,26-temp); 106 } 107 i--; 108 } 109 ans+=min(lx,rx); 110 } 111 cout<<ans<<endl; 112 return 0; 113 } View Code

?

D. Valid Sets

?

As you know, an undirected connected graph with?n?nodes and?n?-?1?edges is called a?tree. You are given an integer?d?and a tree consisting of?n?nodes. Each node?i?has a value?ai?associated with it.

We call a set?S?of tree nodes?valid?if following conditions are satisfied:

S?is non-empty.

S?is connected. In other words, if nodes?u?and?v?are in?S, then all nodes lying on the simple path between?u?and?v?should also be presented in?S.

.

Your task is to count the number of valid sets. Since the result can be very large, you must print its remainder modulo?1000000007(109?+?7).

題目：要求所給的樹中，滿足任意兩個節點的權值相差小于等于d的子樹個數。

分析：樹形dp。

為了方便計數，我采取以下方式：每次選取的子樹都是保證根節點的權值為最大，當然如果單單是這樣的話，權值均相等的子樹是會被重復計數的，因此我在遇到權值相等的情況時，需要保證其結點的標號小于根節點。

1 #include <iostream> 2 #include <sstream> 3 #include <ios> 4 #include <iomanip> 5 #include <functional> 6 #include <algorithm> 7 #include <vector> 8 #include <string> 9 #include <list> 10 #include <queue> 11 #include <deque> 12 #include <stack> 13 #include <set> 14 #include <map> 15 #include <cstdio> 16 #include <cstdlib> 17 #include <cmath> 18 #include <cstring> 19 #include <climits> 20 #include <cctype> 21 using namespace std; 22 #define XINF INT_MAX 23 #define INF 0x3FFFFFFF 24 #define MP(X,Y) make_pair(X,Y) 25 #define PB(X) push_back(X) 26 #define REP(X,N) for(int X=0;X<N;X++) 27 #define REP2(X,L,R) for(int X=L;X<=R;X++) 28 #define DEP(X,R,L) for(int X=R;X>=L;X--) 29 #define CLR(A,X) memset(A,X,sizeof(A)) 30 #define IT iterator 31 typedef long long ll; 32 typedef pair<int,int> PII; 33 typedef vector<PII> VII; 34 typedef vector<int> VI; 35 int a[2010]; 36 vector<int>G[2010]; 37 int d,n; 38 const ll MOD=1000000007; 39 ll dp[2010]; 40 void dfs(int v,int u,int root,int x) 41 { 42 if((a[v]<x&&x-a[v]<=d)||(a[v]==x&&root>=v)) 43 { 44 //cout<<v<<" "; 45 dp[v]=1; 46 for(int i=0;i<G[v].size();i++) 47 { 48 if(G[v][i]==u)continue; 49 dfs(G[v][i],v,root,x); 50 dp[v]*=(dp[G[v][i]]+1); 51 dp[v]%=MOD; 52 } 53 54 } 55 return ; 56 } 57 int main() 58 { 59 ios::sync_with_stdio(false); 60 //freopen("in.in","r",stdin); 61 while(cin>>d>>n) 62 { 63 for(int i=0;i<n;i++) 64 { 65 cin>>a[i]; 66 G[i].clear(); 67 } 68 int u,v; 69 for(int i=0;i<n-1;i++) 70 { 71 cin>>u>>v; 72 u--,v--; 73 G[u].PB(v); 74 G[v].PB(u); 75 } 76 ll ans=0; 77 for(int i=0;i<n;i++) 78 { 79 CLR(dp,0); 80 dfs(i,i,i,a[i]); 81 ans+=dp[i]; 82 ans%=MOD; 83 } 84 cout<<ans<<endl; 85 86 } 87 return 0; 88 } View Code

?

E. LIS of Sequence

?

The next "Data Structures and Algorithms" lesson will be about Longest Increasing Subsequence (LIS for short) of a sequence. For better understanding, Nam decided to learn it a few days before the lesson.

Nam created a sequence?a?consisting of?n?(1?≤?n?≤?105) elements?a1,?a2,?...,?an?(1?≤?ai?≤?105). A subsequence?ai1,?ai2,?...,?aik?where?1?≤?i1?<?i2?<?...?<?ik?≤?n?is called increasing if?ai1?<?ai2?<?ai3?<?...?<?aik. An increasing subsequence is called longest if it has maximum length among all increasing subsequences.

Nam realizes that a sequence may have several longest increasing subsequences. Hence, he divides all indexes?i?(1?≤?i?≤?n), into three groups:

group of all?i?such that?ai?belongs to no longest increasing subsequences.

group of all?i?such that?ai?belongs to at least one?but not every?longest increasing subsequence.

group of all?i?such that?ai?belongs to every longest increasing subsequence.

Since the number of longest increasing subsequences of?a?may be very large, categorizing process is very difficult. Your task is to help him finish this job.

Input

The first line contains the single integer?n?(1?≤?n?≤?105) denoting the number of elements of sequence?a.

The second line contains?n?space-separated integers?a1,?a2,?...,?an?(1?≤?ai?≤?105).

Output

Print a string consisting of?n?characters.?i-th character should be '1', '2' or '3' depending on which group among listed above index?ibelongs to.

Sample test(s) input 1
4 output 3 input 4
1 3 2 5 output 3223 input 4
1 5 2 3 output 3133 Note

In the second sample, sequence?a?consists of 4 elements:?{a1,?a2,?a3,?a4}?=?{1,?3,?2,?5}. Sequence?a?has exactly 2 longest increasing subsequences of length 3, they are?{a1,?a2,?a4}?=?{1,?3,?5}?and?{a1,?a3,?a4}?=?{1,?2,?5}.

In the third sample, sequence?a?consists of 4 elements:?{a1,?a2,?a3,?a4}?=?{1,?5,?2,?3}. Sequence?a?have exactly 1 longest increasing subsequence of length 3, that is?{a1,?a3,?a4}?=?{1,?2,?3}.

題目：問所給的序列中，若ai不存在于任何的LIS中，則輸出1，若存在于至少一個但不為全部LIS中，則輸出2，若ai存在于任意一個LIS中，則輸出3

分析：求出到該點（包括該點在內）的正向LIS和不包括該點的反向LIS的長度，通過此判斷即可。

例如：序列?? 1? 2? 4? 2? 3? 5? 4

　　　l[i]???? 1? 2? 3? 2? 3? 3? 4　　表示正向的到該點為止包括該點在內的LIS的長度

　　?? r[i] ? ? 3? 2? 1? 2? 1? 0? 0?? 表示的是反向的到該點為止不包括該點的最長下降子序列的長度

如果對于某一點，若l[i]+r[i]等于LIS的長度，則其必處于某一LIS之中，否則必然不在任意一個LIS之中，可判該點為1

接下來在由于之前我記錄了正向的到該點為止包括該點在內的LIS的長度，即我知道每一個處于LIS中的位置，由此，我只需判LIS中該位置的點是否唯一，若唯一，則為3，否則為2；

1 #include <iostream> 2 #include <sstream> 3 #include <ios> 4 #include <iomanip> 5 #include <functional> 6 #include <algorithm> 7 #include <vector> 8 #include <string> 9 #include <list> 10 #include <queue> 11 #include <deque> 12 #include <stack> 13 #include <set> 14 #include <map> 15 #include <cstdio> 16 #include <cstdlib> 17 #include <cmath> 18 #include <cstring> 19 #include <climits> 20 #include <cctype> 21 using namespace std; 22 #define XINF INT_MAX 23 #define INF 0x3FFFFFFF 24 #define MP(X,Y) make_pair(X,Y) 25 #define PB(X) push_back(X) 26 #define REP(X,N) for(int X=0;X<N;X++) 27 #define REP2(X,L,R) for(int X=L;X<=R;X++) 28 #define DEP(X,R,L) for(int X=R;X>=L;X--) 29 #define CLR(A,X) memset(A,X,sizeof(A)) 30 #define IT iterator 31 typedef long long ll; 32 typedef pair<int,int> PII; 33 typedef vector<PII> VII; 34 typedef vector<int> VI; 35 const int maxn=100010; 36 int a[maxn],b[maxn],dp[maxn]; 37 int l[maxn],r[maxn]; 38 int ans[maxn]; 39 int deg[maxn]; 40 int main() 41 { 42 ios::sync_with_stdio(false); 43 int n; 44 while(cin>>n) 45 { 46 CLR(ans,0); 47 CLR(deg,0); 48 for(int i=0;i<n;i++) 49 { 50 cin>>a[i]; 51 b[n-1-i]=-a[i]; 52 } 53 fill(dp,dp+n,INF); 54 for(int i=0;i<n;i++) 55 { 56 int temp=lower_bound(dp,dp+n,a[i])-dp; 57 l[i]=temp+1; 58 dp[temp]=a[i]; 59 } 60 int len=lower_bound(dp,dp+n,INF)-dp; 61 fill(dp,dp+n,INF); 62 for(int i=0;i<n;i++) 63 { 64 int temp=lower_bound(dp,dp+n,b[i])-dp; 65 r[n-1-i]=temp; 66 dp[temp]=b[i]; 67 } 68 for(int i=0;i<n;i++) 69 { 70 if(l[i]+r[i]==len) 71 { 72 deg[l[i]]++; 73 } 74 else 75 { 76 ans[i]=1; 77 } 78 } 79 for(int i=0;i<n;i++) 80 { 81 if(ans[i])cout<<1; 82 else if(deg[l[i]]>1)cout<<2; 83 else cout<<3; 84 } 85 cout<<endl; 86 87 } 88 return 0; 89 } View Code

?

?

轉載于:https://www.cnblogs.com/fraud/p/4100847.html

總結

以上是生活随笔為你收集整理的Codeforces Round #277(Div 2) A、B、C、D、E题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。