思路 对于大于等于10的数，让每一位相加得到一个新的数，并继续执行此操作。记得测一下1e9，没有异常就可以交了。 代码 #include<bits/stdc++.h> using namespace std; int main(){ int n; scanf("%d",&n); while(n>=10){ int tmp=0; while(n){ tmp+=n%10; n/=10; } n=tmp; } cout<<n; return 0; }

大家应该都是这么写的。 代码 #include<bits/stdc++.h> using namespace std; int main(){ char ch=getchar(); if(ch>='0'&&ch<='9') cout<<1<<endl; else if(ch>='A'&&ch<='Z') cout<<2<<endl; else if(ch>='a'&&ch<='z') cout<<3<<endl; else co...

思路 小常识：string有加法，给定一个新的字符串和旧的字符串，旧字符串每一位替换加到新字符串，递归n次答案就出来了。 代码 #include<bits/stdc++.h> using namespace std; int n; void fc(string str,int cnt){ if(cnt==n){ cout<<str<<endl; return; } string tmp=""; for(int i=0;i<str.length();i++){ if(str[i]=='0') tmp=tmp+"1"...

有兴趣可以用矩阵加速做一下。 简单代码 #include<bits/stdc++.h> using namespace std; typedef long long ll; int n,f[1000005]; int main(){ scanf("%d",&n); f[1]=1,f[2]=1; for(int i=3;i<=n;i++){ f[i]=(f[i-1]+f[i-2])%10007; } cout<<f[n]<<endl; return 0; }

思路 杨辉三角的公式 num[i][j]=num[i-1][j]+num[i-1][j-1];注意格式不要出错就行了。 代码 #include<bits/stdc++.h> using namespace std; int n,num[35][35]; int main(){ memset(num,0,sizeof(num)); scanf("%d",&n); num[1][1]=1;num[2][1]=1;num[2][2]=1; for(int i=3;i<=n;i++){ for(int j=1;j<=i;j++){ num[i][j]...

发个最短题解吧。 #include<bits/stdc++.h> using namespace std; char ch[105]; int main(){ cin>>ch; for(int i=strlen(ch)-1;i>=0;i--) cout<<ch[i]; return 0; }

思路 可以用位运算和前缀和的相关知识。要让X异或a[i]求和最大SUM，则SUM的每一位都是1，我们需要求的是X的每一位该取0还是1。我们可以用一个二维数组a[i][j]记录前i个数第j位是1的个数，这样我们就能知道L~R范围内某一位的0多还是1多。运用异或的性质我们知道，在0多的情况下X那一位该取1，在1多的情况下X那一位该取0；而0和1一样多的时候，根据题意X尽可能小，就取0。 代码 #include<bits/stdc++.h> using namespace std; int n,q,a,l,r; int sm1[100005][32]; //sm[i][j]:第i个数前面...

思路 与<15108道路建设>同解，Kruskal硬过就行了。 代码 #include<bits/stdc++.h> using namespace std; const int maxn=100005,maxm=1000005; struct E{ int from,next,to,dis; }edge[maxm*2]; int n,m,u,v,w; int head[maxn],cnt=0,fa[maxn]; int find(int x){ if(fa[x]==x) return x; else return fa[x]=find(fa[x]); } void u...

思路 最小生成树板子题，用Kruskal硬过就行了。算法流程：初始设点在集合A，无连边；将图中的边按照权值从小到大排序，然后从最小的边开始连接（使用并查集）；将边的两端点加入集合B，如果当前边的两个端点不都在集合A，则进行连接；选择m-1条边的时候刚好将m个点连上，此时判断权值之和是否大于c。 代码 #include<bits/stdc++.h> using namespace std; const int maxn=10005,maxm=100005; struct E{ int from,next,to,dis; }edge[maxm*2]; int c,n,m,u,v,w; ...

回文串 思路 这道题我先写了马拉车（不会的可以去学一学，能以O(n)复杂度求最长回文串长度），A了之后看数据范围，发现暴力也是能过的。需要注意点一些细节：（我被坑过的点）马拉车记得在要在字符串前面加多一个字符防止越界。暴力算法不要列举区间再判断是否回文，先列举中心点再求回文长度更快。同时注意字符串长度的奇偶性。 暴力代码 #include<bits/stdc++.h> using namespace std; int main() { char s[1205]; while(scanf("%s",s)!=EOF){ int len=strlen(s),maxx=...

兔子的序列 思路 打表记录1~1000内所有完全平方数，然后在输入序列的时候剔除掉，那么最大的一个数就是答案。 代码 #include<bits/stdc++.h> using namespace std; int main(){ int n,i,ans=0,a[1005],b,vis[1005]; memset(vis,0,sizeof(vis)); scanf("%d",&n); for(i=0;i*i<=1000;i++){ vis[i*i]=1; } i=0; while(n--){ scanf("%d",&b)...

[NOIP回文日期] 思路 纯模拟题，前面几发没看到范围写错了没过，总的来说还是很简单的。最快的方式是打表，挑出回文日期然后判断每一个回文日期是否在起末日期之间就行了。暴力也是可以过的（估计数据强一点就不一定了），当然要打表就得暴力嘛……如何判断回文？日期是八位整数，使用取模和除法运算就能判断，不建议使用字符串。 暴力的代码 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e4+7; int ans=0,l,r,flag; void check(int x){ if...

[NOIP2005]校门外的树 思路 一开始有l+1棵树，刨去所给范围合并所得后所得的树的个数就是结果。用一个vis数组来记录刨去树的区间（是一个闭区间），数据范围很小，暴力可解。 代码 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e4+7; int main(){ int l,m,x,y,vis[maxn]={0},cnt=0; scanf("%d%d",&l,&m); for(int i=1;i<=m;i++){ s...

#[NOIP2006]明明的随机数# 思路 去重+排序=>计数排序看一眼数据范围完全够用。 代码 #include<bits/stdc++.h> using namespace std; int n,a,cnt=0,mp[1005]={0}; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a); if(!mp[a]){ cnt++; mp[a]=1; } } cout<<cnt<<endl; for(int i=...