CFGoodBye2018

CF1091B

平均数一下

#include<cstdio>
#include<iostream>
#define int long long
using namespace std;
int n,x,y;
signed main(){cin>>n;
    for(int i=1,a,b;i<=n*2;i++)cin>>a>>b,x+=a,y+=b;
    cout<<x/n<<" "<<y/n;
    return 0;
}

CF1091C

题意:1-n 的环上走球,每次走的距离为 k,从 1 号走,直到回到 1,这过程中经过的人的编号之和为这次走球的价值(1 号只算一次),问所有可能的价值,从小到达输出

显然只用考虑 的情况

如果 ,那么只会经过 ,等差数列公式计算即可

那么问题转化为枚举 ,即枚举 的约数

首先 分解质因数,然后在质因数表上 枚举即可

因为 以内的数的互不相同的质因子的个数不超过 10 个,所以复杂度很小

#include<cstdio>
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N=100005;
int n;
int p[N],c[N],cnt;
int ans[N],ant;
void dfs(int k,int cur){if(k>cnt)return;
    for(int i=0;i<=c[k];i++,cur*=p[k]){ans[++ant]=(n+2-cur)*n/cur/2;
        dfs(k+1,cur);
    }
}
signed main(){cin>>n;
    int n2=n;
    for(int i=2;i*i<=n2;i++){if(n2%i==0){p[++cnt]=i;
            while(n2%i==0)++c[cnt],n2/=i;
        }
    }
    if(n2!=1)p[++cnt]=n2,c[cnt]=1;
    dfs(1,1);
    sort(ans+1,ans+ant+1);
    for(int i=1;i<=ant;i++){if(ans[i]==ans[i-1])continue;
        cout<<ans[i]<<" ";}
    return 0;
}

CF1091D

题意自见

总和为 ,就是说 个数刚好是 .

我们发现,两个相同的数字如果距离为 n,那么他们之间一定有这样的子串

定义 表示 n 个数的全排列的子串个数

对于以 开头的这 个连在一起的全排列,除掉 不看,剩下的 个数其实就是 的全排列(离散化的思想),而这 的全排列两两之间加了一个数字 ,对子串的性质没有影响,也就有 的子串

这是从 推过来的,那么有没有新产生的不属于 的子串呢?

有。所谓属于 的子串,其实就是在 的子串的前缀或中间插入 来转化;但是这不包括在它的末尾插入 ,因为 是开头的数

因此,在 子串的末尾插入 的序列,有 个(最后一个全排列的末尾没有 1 了),累加即可

最后,有多少个 呢?显然有 个,那么递推如下

#include<cstdio>
using namespace std;
const int N=1e6+6,P=998244353;
int n;
int f[N],fac[N];
int main(){scanf("%d",&n);
    f[1]=1,fac[1]=1;
    for(int i=2;i<=n;i++){fac[i]=(long long)fac[i-1]*i%P;
        f[i]=(long long)i*(f[i-1]+fac[i-1]-1)%P;
    }
    printf("%d",f[n]);
    return 0;
}

  转载请注明: Sshwy's Blog CFGoodBye2018

 上一篇
[LuoguP2764] 最小路径覆盖问题 [LuoguP2764] 最小路径覆盖问题
DAG 的最小路径点覆盖给定有向图 。设 的一个简单路(顶点不相交的路)的集合。 如果 中每个顶点恰好在 的一条路上,则称 的一个路径覆盖。 中路径可以从 $V
2019.01.05
下一篇 
洛谷冬日绘板那些事 洛谷冬日绘板那些事
前言洛谷的冬日绘板从去年开始,今年是第二次了 去年其实没玩出什么来,今年我和 gavinzheng 联手自动画脚本正在画一个校徽上去 效果 脚本参考的是去年 github 的开源脚本 Enter-tainer. 见这个大佬的博客 今年的参数
2018.12.30
  目录