Codeforces Round #506 (Div. 3)

實(shí)習(xí)期間事不多，對div3 面向題解和數(shù)據(jù)編程了一波

A. Many Equal Substrings

題目鏈接
A題就是找后綴和前綴重合的部分，KMP更快但是數(shù)據(jù)很小我就直接暴力了（其實(shí)是kmp忘了怎么寫了）
注意字符串只含一個字符的特殊情況。

#include<bits/stdc++.h>
using namespace std;
int main()
{int n,k;string s;cin>>n>>k;cin>>s;int t=0;int flag=1;for(int i=0;i<n;i++){if(s[i]!=s[i-1]){flag=0;break;}}if(flag){cout<<s;for(int i=1;i<k;i++)cout<<s[0];}else{for(int i=n-1;i>0;i--){if(s.substr(0,i) == s.substr(n-i,i)){t=i;break;}}cout<<s;for(int i=1;i<k;i++){cout<<s.substr(t,n-t);}
}}

B.Creating the Contest

一開始題目理解錯誤，他要求的一個子序列對于任一aiai都有ai<=2?ai?1ai<=2?ai?1,這題說是子序列不連續(xù)，但是序列是遞增的。所以只要判斷ai?1和ai就行了ai?1和ai就行了 ,因?yàn)?span id="ze8trgl8bvbq" class="MathJax_Preview" style="color: inherit; display: none;">2?ai?1<ai<ai+12?ai?1<ai<ai+1再加上另一個數(shù)而已。且數(shù)字<=1e9所以最多*10101010,然后暴力枚舉乘的數(shù)。求余數(shù)就行了。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
ll a[200010];
ll p=1;
map<int,ll> ma[11];
int digit(ll num)
{int cnt=0;while(num){cnt++;num/=10;}return cnt;
}
ll mypow(ll m, ll n)
{ll res=1;for(int i=1;i<=n;i++){res=res*m;}return res;
}
int main()
{int n,k;cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=10;i++){p=p*10;for(int j=1;j<=n;j++){int  t=(a[j]*p)%k;ma[i][t]++;}}ll ans=0;for(int i=1;i<=n;i++){int l=digit(a[i]);ans += ma[l][(k-a[i]%k)%k];ll tmp = a[i]*mypow(10,l);if((tmp%k+a[i]%k)%k==0){ans--;}}cout<<ans<<endl;
}

E.Tree with Small Distances

這題貪心就行了。對于每個到一大于2的邊來說明顯要把他的父節(jié)點(diǎn)和1連接起來。代碼看的題解，大體的方式就是把端點(diǎn)的狀態(tài)置為2。

#include<bits/stdc++.h>
#define N 200000+10
using namespace std;
vector<int>tree[N];
int ans,n,x,y;
int dfs(int son,int fa=0)
{int x=2;for(int i=0;i<tree[son].size();i++){int u=tree[son][i];if(u!=fa)x=min(x,dfs(u,son));}if(son!=1&&fa!=1&&x==0)ans++;return (x+1)%3;
}
int main()
{scanf("%d",&n);for(int i=1;i<n;i++){scanf("%d %d",&x,&y);tree[x].push_back(y);tree[y].push_back(x);}dfs(1,0);printf("%d\n",ans);return 0;
}

F.Multicolored Markers

從”大到小”遍歷（a+b）的約數(shù)對y1,y2即y1*y2=（a+b），找到一組約數(shù)滿足a或b的約數(shù)對中，存在一組約數(shù)x1,x2,滿足max（y1,y2)>=max(x1,x2) min(y1,y2)>=min(x1,x2),則答案是（y1+y2）*2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{ll s,l;
}g1[200010],g2[200010],g3[200010];
bool cmp(node a,node b)
{return a.s>b.s;
}
int main()
{ll a,b;cin>>a>>b;int cnt1=0;int cnt2=0;int cnt3=0;for(ll i=1;i*i<=a;i++){if(a%i==0){g1[cnt1].l=a/i;g1[cnt1++].s=i;}}for(ll i=1;i*i<=b;i++){if(b%i==0){g3[cnt3].l=b/i;g3[cnt3++].s=i;}}for(ll i=1;i*i<=(a+b);i++){if((a+b)%i==0){g2[cnt2].l=(a+b)/i;g2[cnt2++].s=i;}}sort(g1,g1+cnt1,cmp);sort(g2,g2+cnt2,cmp);sort(g3,g3+cnt3,cmp);int pos = 0;ll ans = 1e18;for(int i=0;i<cnt2;i++){while(pos < cnt1 && g1[pos].s > g2[i].s)pos++;if(g2[i].l < g1[pos].l)continue;if(pos<cnt1){// cout<<pos<<endl;// cout<<g1[pos].l<<' '<<g1[pos].s<<endl;// cout<<"==============="<<endl;// cout<<g2[i].l<<' '<<g2[i].s<<endl;ans=min(ans,(g2[i].s+g2[i].l)*2);break;}}pos=0;for(int i=0;i<cnt2;i++){while(pos < cnt3 && g3[pos].s > g2[i].s)pos++;if(g2[i].l < g3[pos].l)continue;if(pos<cnt3){// cout<<pos<<endl;// cout<<g1[pos].l<<' '<<g1[pos].s<<endl;// cout<<"==============="<<endl;// cout<<g2[i].l<<' '<<g2[i].s<<endl;ans=min(ans,(g2[i].s+g2[i].l)*2);break;}}cout<<ans<<endl;
}

總結(jié)

以上是生活随笔為你收集整理的Codeforces Round #506 (Div. 3)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。