菜鸟测试
A 签到题
链接：http://222.204.56.169/contest/20/problem/A
题意：
找规律签到
题解：
按照给的代码多组输入一下，找到规律，写出来即可
代码：
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
if(n&1)printf("1");else printf("-1");
return 0;
}B 阶乘
链接：http://222.204.56.169/contest/19/problem/B
题意：
找一个数后面有几个0
题解：
其实就是因子中有多少个5，因为5存在一个5前面就有一个2，就是找因子中存在5的个数，例如：n=31中，有因子-> 5 10 15 20 25 30 (31/5=6就是代表这几个数的个数） 然后每五个这样连续的数就会出现5*5这样的数，所以（得到的6/5=1）再加进去直到n=0为止
代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long n,num;
cin>>n;
num=0;
while(n!=0)
{
num=num+n/5;
n=n/5;
}
cout<<num<<endl;
return 0;
}C 合并滑稽
链接：http://222.204.56.169/contest/19/problem/C
题意：
把一串数并在一起，每一次需要消耗对应的数相加的体力。使得体力消耗最小。
题解：
每一次的合并，之前的数都要算一遍，也就是说小的数线合并所消耗的体力会最小，只要每次都用一个sort排序就好了。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[100005];
int main()
{
int n;
scanf("%d",&n);
memset(a,0,sizeof(a));
for(int i=0;i<n;i++)
{scanf("%d",&a[i]);}
int ans=0;
for(int i=0;i<n-1;i++)
{
sort(a,a+n);
a[i+1]+=a[i];
ans+=a[i+1];
a[i]=0;
}
printf("%d",ans);
return 0;
}D ff爱组合数
链接：http://222.204.56.169/contest/19/problem/D
题意：
就是求C_n^m的组合数%p
题解：
可以利用递推（具体的实践在算法笔记P186）
代码：
#include<iostream>
#include<cstdio>
using namespace std;
const int p=1e9+9;
int res[20009][2009]={0};
int n,m;
void calC(int x)
{
for(int i=0;i<x;i++)
{
res[i][0]=res[i][i]=1;
}
for(int i=2;i<=x;i++)
{
for(int j=0;j<=i/2;j++)
{
res[i][j]=(res[i-1][j]+res[i-1][j-1])%p;
res[i][i-j]=res[i][j];
}
}
}
int main()
{
int T;
scanf("%d",&T);
int n,m;
calC(2000);
while(T--)
{
scanf("%d%d",&n,&m);
printf("%d\n",res[n][m]);
}
return 0;
}E 猜猜在哪里
链接：http://222.204.56.169/contest/19/problem/E
题意：
题解：
注意：我不会呀~~呜呜呜呜
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 10;
typedef long long LL;
const LL MOD = 998244353;
LL mpow(LL a, LL x) {
if (x == 0) return 1;
LL t = mpow(a, x>>1);
if (x % 2 == 0) return t * t % MOD;
return t * t % MOD * a % MOD;
}
struct Nod {
LL k, b, s;
Nod operator + (const Nod & o) const {
Nod ans;
ans.k = 1; ans.b = 0;
ans.s = (s + o.s) % MOD;
return ans;
}
} nod[N << 2];
void build(int l,int r,int rt){
if(l==r){
nod[rt].k=1,nod[rt].b=0;nod[rt].s=0; return;
}
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
nod[rt] = nod[rt<<1] + nod[rt<<1|1];
}
void upd(int rt, LL k, LL b) {
nod[rt].k = nod[rt].k * k % MOD;
nod[rt].b = (nod[rt].b * k + b) % MOD;
nod[rt].s = (nod[rt].s * k + b) % MOD;
}
void pushdown(int rt) {
upd(rt<<1, nod[rt].k, nod[rt].b);
upd(rt<<1|1, nod[rt].k, nod[rt].b);
nod[rt].k = 1, nod[rt].b = 0;
}
void update(int l,int r,int rt,int L,int R,LL k,LL b){
if (L<=l&&r<=R) {
upd(rt, k, b); return;
}
pushdown(rt); int mid=(l+r)>>1;
if(L<=mid) update(l,mid,rt<<1,L,R,k,b);
if(R >mid) update(mid+1,r,rt<<1|1,L,R,k,b);
nod[rt]=nod[rt<<1]+nod[rt<<1|1];
}
int query(int l,int r,int rt,int pos){
if(l==r){
return nod[rt].s;
}
pushdown(rt); int mid=(l+r)>>1;
if(pos<=mid) return query(l,mid,rt<<1,pos);
return query(mid+1,r,rt<<1|1,pos);
}
void modify(int l,int r,int rt,int pos,int x){
if(l==r){
nod[rt].s=x; return;
}
pushdown(rt); int mid=(l+r)>>1;
if(pos<=mid) modify(l,mid,rt<<1,pos,x);
else modify(mid+1,r,rt<<1|1,pos,x);
nod[rt] = nod[rt<<1] + nod[rt<<1|1];
}
int t;LL n, m, k;
bool flag[N]; int item1[N], item2[N];
LL inv(LL x){
return mpow(x%MOD, MOD-2);
}
const bool CHK = 0;
LL A[N];
void ran_swap() {
// tot = 1, myval = x
// N: (n-2)/n * x
// Y: 2/(n(n-1)) * (1 - x)
// [(n-2)/n - 2/(n(n-1))] * x + 2/(n(n-1))
LL k = (n-2)*inv(n) - 2*inv(n*(n-1)); k = (k % MOD + MOD) % MOD;
LL b = 2*inv(n*(n-1)); b = (b % MOD + MOD) % MOD;
update(1,n,1,1,n,k,b);
if (CHK) {
for (int i = 1; i <= n; i ++) {
LL ans = (n-2) * inv(n) % MOD * A[i] % MOD;
ans += 2 * inv(n) % MOD * ( (1 - A[i] + MOD) % MOD * inv(n-1) % MOD ) % MOD;
ans %= MOD;
A[i] = ans;
}
}
}
void _swap(int x, int y) {
int v1 = query(1,n,1,x);
int v2 = query(1,n,1,y);
modify(1,n,1,x,v2);
modify(1,n,1,y,v1);
if (CHK) swap(A[x], A[y]);
}
void chk() {
for (int i = 1; i <= n; i ++) {
printf("# %lld %d\n", A[i], query(1,n,1,i));
assert(A[i] == query(1,n,1,i));
}
}
int main() {
scanf("%d", &t);
while (t --) {
scanf("%lld%lld%lld", &n, &m, &k);
build(1, n, 1); modify(1, n, 1, 1, 1);
for (int i = 1; i <= n; i ++) A[i] = 0; A[1] = 1;
for (int i = 1; i <= m; i ++) {
flag[i] = 0;
}
for (int i = 1; i <= k; i ++) {
int op,x,y; scanf("%d%d%d",&op,&x,&y);
flag[op] = 1; item1[op] = x, item2[op] = y;
}
for (int i = 1; i <= m; i ++) {
if (flag[i]) {
_swap(item1[i], item2[i]);
} else {
ran_swap();
}
}
if (CHK) {
chk();
}
for (int i = 1; i <= n; i ++) {
printf("%d%c", query(1,n,1,i),i==n?'\n':' ');
}
LL s = 0;
for (int i = 1; i <= n; i ++) {
s += query(1,n,1,i);
s %= MOD;
}
assert(s == 1);
//printf("sum = %lld\n", s);
}
}
F 约数的个数
链接：http://222.204.56.169/contest/19/problem/F
题意：
f(n)为n约数的个数，求F（n）=1f(1)+2f(2)+、、、+n*f(n)
题解：神奇的筛法
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j+=i)
F[j]++;注意：自行理解，其实表示的就是i为约数的时候，每一个n以内的数都会进行一个计算作为i的倍数对应数字j的约数个数+1，这样其实就是算出来了n以内的所有不同数字对应的约数个数。然后叠加一下就可以啦~
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
ll f[1000006];
ll F[1000006];
void iserv(ll n)
{
for(ll i=1;i<=n;i++)
for(ll j=i;j<=n;j+=i)
f[j]++;
}
int main()
{
ll x;
scanf("%lld",&x);
memset(f,0,sizeof(f));
iserv(x);
F[1]=1*f[1];
for(ll i=2;i<=x;i++)
{
F[i]=F[i-1]+i*f[i];
}
printf("%lld",F[x]);
return 0;
}
曼迪匹艾公司福利 114人发布
