1、签到题
不解释
2、序列2
应该也不难吧 没代码
3、数字串
题解：n的范围是1≤n≤1000,所以这道题直接预处理前1000个数就行。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int a[N],b[N];
int main()
{
int tt;
cin>>tt;
int t=1;
for(int i=1;t<N;i++)
{
int sum=i,p=0;
while(sum) b[p++]=sum%10,sum/=10;
for(int j=p-1;j>=0;j--) a[t++]=b[j];
}
while(tt--)
{
int n;
cin>>n;
cout<<a[n]<<endl;
}
return 0;
}
4、四则运算
这里有一个我自己写的特别长的代码，大家可以参考，也可以百度
//计算表达式
#include<cstring>
#include<iostream>
using namespace std;
char s[100];
int numb[100];
char f[100];
int k=0,k1=0;
void trans()
{
for(int i=0;i<strlen(s);i++)
{
if(s[i]<='9'&&s[i]>='0')
{
numb[k]=numb[k]*10+s[i]-'0';
}
else{
f[k1++]=s[i];
k++;
}
}
}
int main(){
cin>>s;
int sum;
trans();
for(int i=0;i<k1;i++)
{
if(f[i]=='*')
{
numb[i]*=numb[i+1];
for(int j=i+1;j<k;j++)
numb[j]=numb[j+1];
for(int j=i;j<k1;j++)
f[j]=f[j+1];
k1--;
k--;
}
if(f[i]=='/')
{
numb[i]/=numb[i+1];
for(int j=i+1;j<k;j++)
numb[j]=numb[j+1];
for(int j=i;j<k1;j++)
f[j]=f[j+1];
k1--;
k--;
}
}
for(int i=0;i<k1;)
{
if(f[i]=='+')
{
numb[i]+=numb[i+1];
for(int j=i+1;j<k;j++)
numb[j]=numb[j+1];
for(int j=i;j<k1;j++)
f[j]=f[j+1];
k1--;
k--;
}
if(f[i]=='-')
{
numb[i]-=numb[i+1];
for(int j=i+1;j<k;j++)
numb[j]=numb[j+1];
for(int j=i;j<k1;j++)
f[j]=f[j+1];
k1--;
k--;
}
}
cout<<numb[0]<<endl;
}
5、亲子鉴定s
字符串比较，可以先把所有字母变大小写再strcmp
#include<stdio.h>
#include<string.h>
int main()
{
int i=0;
char s1[2000],s2[2000];
scanf("%s",s1);
scanf("%s",s2);
while(s1[i]!='\0')
{
if(s1[i]>=65&&s1[i]<=90)
s1[i]+=32;
i++;
}
i=0;
while(s2[i]!='\0')
{
if(s2[i]>=65&&s2[i]<=90)
s2[i]+=32;
i++;
}
i=0;
while(s1[i]==s2[i]&&s1[i]!='\0')
i++;
if(s1[i]>s2[i])
printf("%d",1);
else if(s1[i]<s2[i])
printf("%d",-1);
else if(s1[i]==s2[i])
printf("%d",0);
return 0;
}
6、协会解散
这个就是概率题
#include <bits/stdc++.h>
using namespace std;
int t;
double p;
int main(){
scanf ("%d", &t);
while (t --){
scanf ("%lf", &p);
printf ("%.6lf\n", min(1.0 * p / (1 - p), 1.0));
}
return 0;
}
7、有趣的定理
//cf304 A
//2013-06-05-18.14
#include <stdio.h>
#include <math.h>
int main()
{
int n;
while (scanf("%d", &n) != EOF)
{
int cnt = 0;
for (int i = 1; i < n; i++)
{
for (int j = 1; j < i; j++)
{
int t = i*i + j*j;
int c = (int)sqrt(t);
if (c > n)
continue;
if (c*c != t)
continue;
if (i+j > c && i+c > j && j+c > i && i-j < c && i-c < j && j-c < i)
cnt++;
}
}
printf("%d\n", cnt);
}
return 0;
}
8、仙女的游戏
前缀和
#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;
const int N = 1e5 + 50;
int n, m, l, t;
int v[N];
ll s[N];
int main()
{
cin >> n >> m;
for(int i = 1 ; i <= n; i ++ ){
cin >> v[i];
s[i] += s[i - 1] + v[i];
}
for(int i = 1; i <= m; i ++ ){
cin >> l >> t;
cout << s[t] - s[l - 1] << endl;
}
return 0;
}
9、表现字符
鸽笼原理:
字符串 s 的所有长度不小于 k 的子串都包含字符 c 相当于长度为 k的子串都包含字符 c，因为长度大于 k 的子串肯定包含了长度为 k 的子串，不妨枚举每一个字母在字符串中出现的位置，任意地，设其出现的相邻位置为 (i,j)（包括头和尾），为了使该字母在所有的长度为 k 的子串中都出现，k至少为 j−i 的最大值，否则会存在一个相邻的位置 (i,j)，中间存在一个子串不包括该字母，对所有这样的字母取min即可
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, M = 26;
int n;
char str[N];
int last[M], d[M];
int main()
{
scanf("%s", str + 1);
n = strlen(str + 1);
for (int i = 1; i <= n; i ++ )
{
int x = str[i] - 'a'; //把每个字符都映射到为0-25
d[x] = max(d[x], i - last[x]);//计算字符x+'a'的最大间距，last[x]为上一次出现的下标
last[x] = i; //记录字符x+'a'的位置
}
for (int i = 0; i < 26; i ++ )
d[i] = max(d[i], n + 1 - last[i]);//处理字符i+'a'最后出现的位置到结束的长度
int res = N + 1;
for (int i = 0; i < 26; i ++ )
res = min(res, d[i]); //取26个字母中间距最小的那位
printf("%d\n", res);
return 0;
}
10、01串
DP+前缀和
思路1：
状态：dp [i] [0] 表示字符串第i位为0的优秀字符串的个数
状态计算：
dp [i] [1] 表示字符串第i位为1的优秀字符串的个数
那么长度为i的游戏字符串个数即为dp [i] [0] + dp [i] [1]
前缀和数组f[i]累加长度小于等于i的个数之和
[l,r]范围内的所有 01 字符串中优秀字符串的数量即为：f[r]-f[l-1]
复杂度：（O(n)）
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110000,mod=1e9+7;
int t,k;
int dp[N][2],f[N];
int main()
{
cin>>t>>k;
for(int i=0;i<k;i++) dp[i][0]=1,f[i]=i;
for(int i=k;i<=100010;i++)
{
dp[i][0]=(dp[i-1][0]+dp[i-1][1])%mod;
dp[i][1]=(dp[i-k][0]+dp[i-k][1])%mod;
f[i]=((f[i-1]+dp[i][0])%mod+dp[i][1])%mod; //前缀和数组
}
while(t--)
{
int l,r;
cin>>l>>r;
cout<<(f[r]-f[l-1]+mod)%mod<<endl;
}
return 0;
}
思路2：
状态：dp[i] 表示所有长度为i的游戏字符串
考虑第i位是0时,表示第i位不影响前面i-1位,即可直接由dp[i-1]转换过来
考虑第i位是1时,表示最近的k位都必须是1,即i-k+1到i这k位都已经确定(必须为1)，即前i-k位不被影响，可由dp[k-1]转换过来。
前缀和数组f[i]累加长度小于等于i的优秀字符串个数之和
[l,r]范围内的所有 01 字符串中优秀字符串的数量即为：f[r]-f[l-1]
复杂度：（O(n)）
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, mod = 1e9 + 7;
int t, k;
int dp[N];
int f[N];
int main()
{
cin>>t>>k;
dp[0] = 1;
for (int i = 1; i < N; i ++ )
{
dp[i] = dp[i - 1]; //i位为0
if (i >= k) dp[i] = (dp[i] + dp[i - k]) % mod;//i位为1
}
for (int i = 1; i < N; i ++ ) f[i] = (dp[i] + f[i - 1]) % mod;//求前缀和
while (t -- )
{
int l, r;
cin>>l>>r;
cout<<(f[r]-f[l-1]+mod)%mod<<endl;
}
return 0;
}
11、CDTU运动会
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll a[2010];
ll dp[2010][2010];
int main()
{
int n;
cin>>n;
for(int i=1 ; i<=n ; i++) cin>>a[i];
sort(a+1,a+1+n);
for(int len=1 ; len<=n ; len++)
{
for(int j=1 ; j+len<=n ; j++)
{
int l=j,r=j+len;
dp[l][r]=min(dp[l][r-1],dp[l+1][r])+(a[r]-a[l]);
}
}
cout<<dp[1][n]<<endl;
return 0;
}
12、路径权值最大
前置知识： 1、拓扑图和拓扑排序
2、DAG 图定义：如果一个有向图无法从任意顶点出发经过若干条边回到该点，则这个图就是有向无环图。所以一个 DAG 图是没有自环和回路的。
题目分析： 如果题目中存在自环和回路，环上所有点的字母都会出现无穷多次，就不可能存在出现次数最多的情况。
若没有自环和回路，路径长度一定是有限值，一定有解。
路径长度最大为 n
如何判断有无环存在： 常用方法：
1、Topsort
2、有向图的强连通分量
如果不存在环，怎么求最长路径？ 每个点会分配一个小写字母，出现次数最多的字母，一共只有 26 种，而每个点的权值只有 26 种，可以考虑枚举每个字母为最大值的情况，最后求一个max。
以a为例
如果一个点的字母是a，则点权为 1，否则为 0。
即在这个拓扑图上求最长路，可以用递推和 DP 来求，
对于已经求好的拓扑序列，倒序使用递推求最长路即可。
这里稍微解释一下为什么可以这么做：
首先要理解一下拓扑序列的含义，这里我们可以使用拓扑排序的方式来判断该图是否是 DAG 图，如果是，则队列q[]中存放的就是一个拓扑序列，那么我们可以从后往前倒推，用闫氏 DP 分析法来分析：
闫氏 DP 分析法： 状态表示（在拓扑序列中）：
集合：f[t] 表示所有以 t 为起点的路径构成的集合 属性：集合中所包含路径长度的最大值
状态计算：
这样，我们在拓扑序列中从后往前递推，就可以算出权值最大的路径和最大路径权值了。
时间复杂度: O(26⋅n)。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 300010, M = N;
int n, m;
char w[N]; //每个点对应的字母
int h[N], e[M], ne[M], idx;//领接表
int q[N], d[N];//q[N]存topsort数组，d[N]存每个点的入度
int f[N]; // 每个点的最长路
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
bool topsort()
{
int hh = 0, tt = -1;
for (int i = 1; i <= n; i ++ )
if (!d[i])
q[ ++ tt] = i; //先把所有入度为0的点加入
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; ~i; i = ne[i]) //遍历每个点的出边
{
int j = e[i];
-- d[j];
if (!d[j]) q[ ++ tt] = j; //存入入度变为0的点
}
}
return tt == n - 1; //如果n个点都存入，说明有topsort序列，图中没有环
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
scanf("%s", w + 1); // 读入每个点的字母
while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);//加边
++ d[b];//加入度
}
if (!topsort()) puts("-1");
else
{
int res = 0; // 答案，最大值
for (char c = 'a'; c <= 'z'; c ++ )
for (int i = n - 1; i >= 0; i -- )
{
// q[i]为当前点
int t = q[i];
// 看一下当前这个点权值为多少。
int v = w[t] == c;
// f[t] 表示以t为起点的长度的最大值
f[t] = v;
// t不一定有后继，如果有后继，则遍历所有t的出边
for (int j = h[t]; ~j; j = ne[j])
{
int k = e[j];
f[t] = max(f[t], v + f[k]);
}
res = max(res, f[t]);
}
printf("%d\n", res);
}
return 0;
}
京公网安备 11010502036488号