发表于 | 评论数：

CF1269C
题意是给你一个n长度的字符串和k，且满足a[i]=a[i+k]对于答案的字符串且得保证答案的字符串在数学上大于等于原来的字符串且最小
这里直接先按照要求更改如果满足条件那么无需继续更改直接输出否则的话我们进行一波遍历，从k~1遍历如果能找到第一个非9的数那么这个相连的数列里的数都加1然后输出答案，否则把9变为0继续遍历这样能够保证最小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(0);
	int n,k;
	string s,ss;
	cin>>n>>k>>s;
	ss=s;
	for(int i=0;i+k<s.size();i++)
	s[i+k]=s[i];
	if(s>=ss)
	cout<<n<<"\n"<<s;
	else
	{
		for(int i=k-1;i>=0;i--)
		{
			if(s[i]!='9')
			{
				for(int j=i;j<s.size();j+=k)
				s[j]++;
				break;
			}
			else
			{
				for(int j=i;j<s.size();j+=k)
				s[j]='0';
			}
		}
		cout<<n<<"\n"<<s;
	}
}

CF1269D
题意给你一个递减的数列代表高度问你最多能用多少1x2或者2x1的多米诺填充原来的图形
黑白交替填色，满足相同的颜色不相邻然后取黑色白色最小值即可，因为一个可用的多米诺一定占一个黑色和一个白色按照这样的填涂方式 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(0);
	long long n,w=0,b=0,x,jk1=0,jk2=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		jk1=x/2+(x%2);
		jk2=x-jk1;
		if(i&1)
		w+=jk1,b+=jk2;
		else
		w+=jk2,b+=jk1;	
	} 
	cout<<min(w,b);
}

发表于 | 更新于 | 评论数：

题意给你a,b,c,d四个数a+b+c+d<=1e5表示有a个0 b个1 c个2 d个3请问能否恰好用这a+b+c+d个数构成一个数列使得数列的每一项满足|xi-xi+1|=1 (1=<i<n)
不是很好想也不是很好做，实际上我们可以直接构造枚举一下abcd谁当起始的位置然后直接构造看能不能完全构造出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
int a[1000005],ans[1000005],p,s,re[1000005];
int main()
{
	ios::sync_with_stdio(0);
	for(int i=0;i<4;i++)
	cin>>a[i],s+=a[i];
	for(int k=0;k<4;k++)
	if(a[k])
	{
		for(int i=0;i<4;i++)
		re[i]=a[i];
		int p=0;
		ans[++p]=k;
		re[k]--;
		int jk=k;
		for(int i=1;i<=s-1;i++)
		{
			if(re[jk-1])
			{	
				ans[++p]=jk-1;
				re[jk-1]--;
				jk--;
			}
			else if(re[jk+1])
			{
				ans[++p]=jk+1;
				re[jk+1]--;
				jk++;
			}
			else break;
		}
		if(p==s)
		{
			cout<<"YES\n";
			for(int i=1;i<=p;i++)
			cout<<ans[i]<<" ";
			return 0;
		}
	}
	cout<<"NO";
}

发表于 | 更新于 | 评论数：

[CQOI2007]余数求和

纯数论分块板子题不谈~不过要注意右边界不要大于n，因为k可能大于n，并且注意除以0的情况就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
int main()
{
	long long n,m,ans=0;
	scanf("%lld%lld",&n,&m);
	ans+=n*m;
	for(long long l=1,r=0;l<=n;l=r+1)
	{
		if(m/l) r=min(n,m/(m/l));
		else r=n;
		ans-=(m/l)*(l+r)*(r-l+1)/2;
	}
	printf("%lld",ans);
}

[清华集训2012]模积和

先算出全部的然后减去i=j的。注意这里i=j的时候需要化简(n-[n/i]i)(m-[m/i]i)化简出来四项式子之后我们数论分块的r标准为min(n/(n/l),m/(m/l))即可
注意平方和公式为x(x+1)*(2x+1)/6 

#include <bits/stdc++.h>
using namespace std;
long long mod=19940417;
long long sum(long long x)
{
    return x%mod*(x+1)%mod*(2*x+1)%mod*3323403%mod;
}
int main()
{
    long long ans1=0,ans2=0,ans,jk,n,m,inv=9970209;
    scanf("%lld%lld",&n,&m);
    ans1+=n*n,ans2+=m*m;
    ans1%=mod,ans2%=mod;
    for(long long l=1,r=0;l<=n;l=r+1)
    {
        if(n/l) r=n/(n/l);
        else r=n;
        ans1=ans1%mod-(n/l)%mod*(l+r)%mod*(r-l+1)%mod*inv%mod;
        ans1%=mod;
    }
    for(long long l=1,r=0;l<=m;l=r+1)
    {
        if(m/l) r=m/(m/l);
        else r=m;
        ans2=ans2%mod-(m/l)%mod*(l+r)%mod*(r-l+1)%mod*inv%mod;
        ans2%=mod;
    }
    ans1=(ans1%mod+mod)%mod;
    ans2=(ans2%mod+mod)%mod;
    ans=ans1*ans2;
    ans%=mod;
    jk=min(n,m);
    ans=ans%mod-n%mod*m%mod*jk%mod;
    ans%=mod;
    for(long long l=1,r=0;l<=jk;l=r+1)
    {
        if(n/l||m/l) r=min(n/(n/l),m/(m/l));
        else r=jk;
        ans=ans%mod+m%mod*(n/l)%mod*(l+r)%mod*(r-l+1)%mod*inv%mod+n%mod*(m/l)%mod*(l+r)%mod*(r-l+1)%mod*inv%mod-(n/l)%mod*(m/l)%mod*(sum(r)%mod-sum(l-1)%mod)%mod;
        ans%=mod;
    }
    printf("%lld",(ans%mod+mod)%mod);
}

发表于 | 评论数：

题目大意

题意是给定2*N-1个篮子里面分别含有ai个苹果bi个橘子问能否选择出N个篮子使得所有篮子里面的苹果个数大于等于总苹果个数的一半且所有的橘子个数大于等于所有橘子个数的一半

思路

我们按照一个值排序，这里选择苹果把他升序排列然后我们按照奇数下标选取橘子或者按照偶数下标选取，如果按照奇数下标选取的橘子满足条件那么就是这么选否则是偶数下标加上2*N-1下标

解释

首先我们这么做能保证苹果是一定满足条件的因为an>an-1 an-2>an-3 … a3>a1所以加起来也一定是满足条件的，那么剩下的就是如果奇数个橘子满足条件那么就是否则就选偶数个再加最后一个
我们假设奇数个橘子的重量为A,那么偶数个为A’那么A+A’=sum且A < sum/2 那么sum-A’ < sum/2 移项得到 A’ > sum/2 再加上最多的苹果肯定是满足条件的且现在苹果满足a2>a1 a4>a3 再加上一个a2*n-a肯定也是满足条件的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;
const int N=200005;
struct node
{
	long long l,r,id;
}a[N],b[N];
bool c1(node a,node b)
{
	return a.l<b.l;
}
bool c2(node a,node b)
{
	return a.id<b.id;
}
int main()
{
	ios::sync_with_stdio(0);
	int t;
	cin>>t;
	while(t--)
	{
		long long jk1=0,jk2=0,s1=0,s2=0;
		int n,p=0;
		cin>>n;
		for(int i=1;i<=2*n-1;i++)
		cin>>a[i].l>>a[i].r,jk1+=a[i].l,jk2+=a[i].r,a[i].id=i;
		sort(a+1,a+2*n,c1);
		for(int i=1;i<=2*n-1;i++)
		if(i&1) s1+=a[i].r;
		else s2+=a[i].r;
		if(s1>=jk2/2+(jk2%2!=0))
		{
			cout<<"YES\n";
			for(int i=1;i<=2*n-1;i+=2)
			b[++p]=a[i];
			sort(b+1,b+1+p,c2);
			for(int i=1;i<=p;i++)
			cout<<b[i].id<<" ";
			cout<<"\n";
		}
		else if(s2>=jk2/2+(jk2%2!=0))
		{
			cout<<"YES\n";
			b[++p]=a[2*n-1];
			for(int i=2;i<=2*n-1;i+=2)
			b[++p]=a[i];
			sort(b+1,b+1+p,c2);
			for(int i=1;i<=p;i++)
			cout<<b[i].id<<" ";
			cout<<"\n";
		}
		else
		cout<<"NO\n";
	}
}

发表于 | 更新于 | 评论数：

我真的说实话这套题感觉弄得很仓促，但是也是存在不错的题目的
目前已补：
01 03 06 07 08 09 10 11
目前未补：
02 04 05 12

1001 Zeckendorf(规律)

这个直接找规律看看就行了，也没几个斐波那契数的，我这里直接暴力求解的。实际上所有的数都可以被斐波那契数拆分然后一个一个找最大的减去就行了 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
long long a[1005];
int main()
{
	a[1]=1,a[2]=1;
	for(int i=3;i<=92;i++)
	a[i]=a[i-1]+a[i-2];
	long long n;
	while(~scanf("%lld",&n))
	{
		if(n==0)
		continue;
		while(n)
		{
			int pos,f=0;
			for(int i=1;i<=92;i++)
			{
				pos=i;
				if(a[i]>=n)
				{
					if(a[i]>n)
					f=1; 
					break;
				}
			}
			if(f)
			{
				n-=a[pos-1];
				printf("%lld%c",a[pos-1],n?' ':'\n');
			}
			else
			{
				n-=a[pos];
				printf("%lld%c",a[pos],n?' ':'\n');
			}
		}
	}
}

1002 This brave man is super strong but super cautious!(字符串模拟)

究极恶心的模拟，说也感觉说的不是多么清楚，还有人能做出来真的是太强了，我是直接恶心到了不做了，一直做不对

1003 Interstellar(数学结论+猜谜)

赛场能做出来的要么是知道结论的，要么就是老猜谜家了，这种猜谜东西我是之前不知道的。我看了看二维三维的结论发现了三维空间的要用二维空间的去推那么我们可以注意到n维空间的可以用n-1维空间的推出那么我们的公式就是

f[n]=f[n-1]+g[n-1]

f代表当前的维数n个上一维数所能弄出来的部分,g代表上一维 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
const int N=200005;
long long f[6][N]; 
int main()
{
	for(int i=1;i<=16000;i++)
	f[0][i]=1;
	for(int i=0;i<=5;i++)
	f[i][0]=1;
	for(int i=1;i<=5;i++)
	{
		for(int j=1;j<=16000;j++)
		f[i][j]=f[i][j-1]+f[i-1][j-1];
	}
	int t;
	scanf("%d",&t);
	while(t--)
	{
		long long n,m;
		scanf("%lld%lld",&n,&m);
		printf("%lld\n",f[n][m]);
	}
}

1004 Rubik’s cube Simulator(不明)

看着一堆英文和这复杂的样例，这应该是个原题。。。但是我也不大想看了

1005 柳予欣和她的女朋友们(不明)

像是一个图论，但是我现在图论也不会多少，反正我是不会

1006 柳予欣的舔狗行为(暴力)

直接把要的东西搞出来就行了，然后直接按照询问输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
long long a[100005],pre[100005],p;
int main()
{
	int cnt=1;
	while(1)
	{
		if(p>100000)
		break; 
		for(int j=1;j<=cnt;j++)
		a[++p]=cnt;
		cnt++;
	}
	memset(pre,0,sizeof(pre));
	for(int i=1;i<=100001;i++)
	pre[i]=pre[i-1]+a[i];
	long long n;
	scanf("%lld",&n);
	printf("%lld",pre[n]);
}

1007 柳予欣和她女朋友的购物计划(小凯的疑惑)

1
2
3
4
5
6
7
8
#include <bits/stdc++.h>
using namespace std;
int main()
{
	long long a,b;
	scanf("%lld%lld",&a,&b);
	printf("%lld",a*b-a-b);
}

1008 柳予欣不想挂科(思维)

老思维题了，我这想了得快2h才交的，没想到运气好一遍过了。如果我去现场赛的话做出5题或许还能搞搞这题的一血，也不一定我比较喜欢跟榜也。
经过深思熟虑发现规律就是如果有下降后上升的数在数组里面那么他就能分出来一堆的块，我们画图可以知道这些块能额外提供一些操作，于是我们找规律就能得到一些规律。具体看代码吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
const int N=200005;
long long maxn=0,re=0,a[N],ans=0,now=0;
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%lld",&a[i]);
	now=a[1];
	for(int i=2;i<=n-1;i++)
	{
		now=max(now,a[i]);
		if(a[i]<a[i-1]&&a[i]<=a[i+1])
		ans+=now,ans-=a[i],now=0;
	}
	now=max(now,a[n]); 
	ans+=now;
	printf("%lld",ans);
}

1009 柳予欣的女朋友们在分享水果(坑人的签到题)

注意2分解后为两个1都是奇数！！！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	scanf("%d",&n);
	if(n==2||(n&1))
	printf("NO");
	else
	printf("YES"); 
}
```	  
# 1010 FFFFFunctions(GCD)
看过欧几里得算法的应该都能一眼看出这是什么题吧
```cpp
#include <bits/stdc++.h>
using namespace std;
int a[1000005],p[1000005];
int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
		for(int i=1;i<=n;i++)
		scanf("%d",&p[i]);
		int ans=0;
		for(int i=1;i<=n;i++)
		ans=__gcd(ans,a[p[i]]);
		if(ans)
		printf("%d\n",ans);
	}
}

1011 Solved Math problem(莫比乌斯反演)

SDOI原题，还有规律，我直接糊的板子我也不会

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =200005;
ll p[N],bk[N],mu[N],q,pre[N],now[N],mod=998244353;
void get()
{
	mu[1]=1;
	for(int i=2;i<=100000;i++)
	{
		if(!bk[i])
		p[++q]=i,mu[i]=-1;
		for(int j=1;j<=q&&i*p[j]<=N-5;j++)
		{
			bk[i*p[j]]=1;
			if(i%p[j]==0)
			break;
			mu[i*p[j]]=-mu[i];
		}
	}
	for(int i=1;i<=100000;i++)
	pre[i]=pre[i-1]%mod+mu[i]%mod,pre[i]%=mod;
	for(int i=1;i<=100000;i++)
	{
		ll ans=0;
		for(ll l=1,r=0;l<=i;l=r+1)
		{
			r=i/(i/l);
			ans=ans%mod+(r-l+1)%mod*(i/l)%mod,ans%=mod;
		}
		now[i]=ans%mod;
	}
}
int main()
{
	get();
	ll t;
	ll n,m;
	while(~scanf("%lld%lld",&n,&m))
	{
		ll ans=0;
		for(ll l=1,r=0;l<=min(n,m);l=r+1)
		{
			r=min(n/(n/l),m/(m/l));
			ans=ans%mod+(pre[r]-pre[l-1])%mod*now[n/l]%mod*now[m/l]%mod,ans%=mod;
		}
		printf("%lld\n",(ans%mod+mod)%mod);
	}
}

1012 柳予欣的背水一战(不明)

我题也没仔细看，我这先鸽子这个吧。似乎出题人还很热情的邀请我去做他的题，可是似乎我这题目都没大想能看懂的样子

0%