小凯的数字

//小凯的数字
//两个重点：
//1、任何数除以9的余数==这个数每一位之和除以9的余数
//2、任意九个等差数列之和是9的倍数
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		long long l,r,ans=0;
		cin>>l>>r;
		int cnt=(r-l+1)%9;
		for(int j=0;j<cnt;j++)
			ans+=l+j;
		cout<<ans%9<<endl;
	}
	return 0;
}

哥德巴赫猜想

#include<bits/stdc++.h>
using namespace std;
bool isp(int x){
	for(int i=2;i*i<=x;i++)
		if(x%i==0) return 0;
	return 1;
}
int main(){
	int n;cin>>n;
	for(int i=2;i<=n;i++){
		if(isp(i)){
			for(int j=i;j<=n;j++)
				if(isp(j) and isp(n-i-j) and n-i-j>=j){
					cout<<i<<" "<<j<<" "<<n-i-j;
					return 0;
				}
		}
	}
	return 0;
}

拼数

#include<bits/stdc++.h>
using namespace std;
bool cmp(string a,string b){
	return a+b>b+a;
}
int main(){
	int n;
	string s[21];
	cin>>n;
	for(int i=0;i<=n-1;i++) cin>>s[i];
	sort(s,s+n,cmp);
	for(int i=0;i<=n-1;i++) cout<<s[i];
	return 0;
}

删树问题

#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;int n;
	cin>>s>>n;
	for(int i=1;i<=n;i++){
		int j=0;int len=s.size();
		for(;j<len-1;j++){
			if(s[j]>s[j+1]){
				s.erase(j,1);
				break;
			}
		}
		if(j==len-1) s.erase(j,1);
	}
	while(s[0]=='0') s.erase(0,1);
	if(s.size()==0) cout<<0;
	else cout<<s;
	return 0;
}

奇怪的电梯

// 线性dp
#include<bits/stdc++.h>
using namespace std;
int go[209],f[209],n,a,b;
int main(){
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++)
		cin>>go[i],f[i]=1e9;
	f[a]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(j+go[j]<=n) f[j+go[j]]=min(f[j+go[j]],f[j]+1);
			if(j-go[j]>=1) f[j-go[j]]=min(f[j-go[j]],f[j]+1);
		}
	}
	if(f[b]==1e9) cout<<-1;
	else cout<<f[b];
	return 0;
}

// dfs
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int q[N];//q为第几层
int k[N];//k存每层上的按钮数字
int a[N];//a走到这一层要几步
int b[N];//这一层是否走过
int main(){
    int x,y,n;//x是出发楼层，y是终点楼层，n总楼层数
    cin>>n>>x>>y;
    for(int i=1;i<=n;i++) cin>>k[i];
    b[x]=1;
    q[1]=x;
    int ll=0,rr=1;
    do{
        ll++;
        for(int i=-1;i<=1;i+=2){//上下两个方向
            int newlou=q[ll]+k[q[ll]]*i;
            if(newlou>0&&newlou<=n&&!b[newlou]){
                rr++;
                q[rr]=newlou;
                b[newlou]=1;
                a[rr]=a[ll]+1;
            }
        }
    }while(ll!=rr&&q[ll]!=y);
    if(x==y)cout<<0<<endl;
    else if(q[ll]==y)cout<<a[ll]<<endl;
    else cout<<-1<<endl;
    return 0;
}