Codeforces Round #506 (Div. 3) (中等难度)
自己的做题速度大概只尝试了 D 题, 不过 TLE
D. Concatenated Multiples
题意
数组 a[], 长度 n, 给一个数 k, 求满足条件的 (i,j)(i!=j) a[i],a[j] 连起来就可以整除 k
连起来的意思是 20,5 连起来时 205; 5,20 连起来时 520
n<=2*1e5,k<=1e9,ai<=1e9
愚蠢的思路是像我一样遍历 (i,j) 可能性, 然后 TLE, 因为这是 O(n^2)
可以先思考一简单问题如何不是连起来而是 a[i]+a[j]如何计算, 很简单将 a[]%k 进行计数, 然后计数(k-a[i])%k, 这时查找只需 O(logn)
这里 a[i]*(10^k),k 实际上只有 10 中可能所以也可以存起来
时间复杂度 O(nlogn)
代码
- #include<bits/stdc++.h>
- const int maxn=200020;
- #define ll long long
- int a[maxn];
- int mod[maxn];
- int ka[maxn];
- int n,k;
- int geth(int x){
- ll mul=1;
- int t=1;
- while(mul<=x){
- mul=mul*10;
- t=(t*(10%k))%k;
- }
- return t;
- }
- int main(){
- scanf("%d %d",&n,&k);
- for(int i=1;i<=n;i++){
- scanf("%d",&a[i]);
- mod[i]=a[i]%k;
- ka[i]=(geth(a[i]))%k;
- }
- ll ans=0;
- for(int i=1;i<=n;i++){//O(n^2)
- for(int j=1;j<=n;j++){
- if(i!=j&&((mod[i]*(ka[j]))%k+mod[j])%k==0){
- //printf("db %d %d\n",i,j);
- ans++;
- }
- }
- }
- printf("%I64d\n",ans);
- }
- E. Tree with Small Distances
题意
这道题还没想出来, 据说使用贪心, 下面是别人代码(感觉大佬的思路都是一样, 应该是触摸到问题本质)
代码
- #include<bits/stdc++.h>
- using namespace std;
- int n;
- const int maxn = 2e5+100;
- vector<int> G[maxn];
- int used[maxn];
- int d[maxn];
- int ans = 0;
- void dfs(int u,int f){
- //cout<<"enter"<<u<<" "<<f<<endl;
- bool flag = false;
- for(int i=0;i<G[u].size();i++){
- int v = G[u][i];
- if(v!=f){
- d[v] = d[u] + 1;
- dfs(v,u);
- flag|=used[v];
- }
- }
- if(d[u]>2&&!used[u]&&!flag&&!used[f]){
- used[f] = true;
- //cout<<"db"<<f<<endl;
- ans++;
- }
- //cout<<"out"<<endl;
- }
- int main(){
- int t;
- //freopen("in.txt","r",stdin);
- scanf("%d",&n);
- for(int i=0;i<n-1;i++){
- int a,b;
- scanf("%d%d",&a,&b);
- G[a].push_back(b);
- G[b].push_back(a);
- }
- dfs(1,0);
- /*
- cout<<"db1\n";
- for(int i=1;i<=n;i++){
- cout<<d[i]<<"\t";
- }
- cout<<endl;
- for(int i=1;i<=n;i++){
- cout<<used[i]<<"\t";
- }
- cout<<"db over"<<endl;
- */
- printf("%d\n",ans);
- //fclose(stdin);
- return 0;
- }
- F. Multicolored Markers
题意
自己看题 http://codeforces.com/problemset/problem/1029/F 吧
枚举较短边, 考虑蓝方块构成矩形的最低高度和红方块构成矩形的最低高度是否和当前高度冲突
代码
- #include<bits/stdc++.h>
- #define ll long long
- int main(){
- ll a,b;
- std::cin>>a>>b;
- ll c=a+b;
- ll tmp=std::max(a,b);
- ll minl=(a+b+1)*2;
- ll lowa=a;
- ll lowb=b;
- for(ll i=1;i*i<=(a+b);i++){
- if(a%i==0) lowa=a/i;
- if(b%i==0) lowb=b/i;
- if(c%i==0){
- if(c/i>=lowa||c/i>=lowb){
- //std::cout<<"db"<<i<<std::endl;
- minl=std::min(2*(i+c/i),minl);
- }
- }
- }
- std::cout<<minl<<std::endl;
- }
加油, 需要补题 Kmp, 数论 + 树
来源: http://www.bubuko.com/infodetail-2742646.html