A 移动的和尚
思路：本题K的数据范围较大，所以直接暴力模拟会超时，所以需要对题目进行分析找出规律进行计算。首先将X转化为X的绝对值，这样方便后面的计算，然后判断走K次不能不走到最靠近原点的距离，如果不能则输出 x-k*d
如果可以则判断还剩下几步，剩下的步骤将会在两个点中反复交替，所以只需要判断剩下步骤的奇偶性即可
AC代码如下：

#include<iostream> #include<cstdio> #include <stdio.h> #include<algorithm> #include<cstring> #include <string> #include<cmath> #include<cstdlib> #include<queue> #include<map> #include<vector> #include<bits/stdc++.h> #include <set> #define ll long long #define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #define inf 0x3f3f3f #define pi 3.98 using namespace std; const int N=2e5+10; const int mod=1e9+7; ll n,k,d; int main() { 
    cin>>n>>k>>d; n=abs(n); ll sum=n/d;//判断走到原点要几步 ll t=n%d; if(sum>k) { 
    cout<<n-k*d<<endl; } else { 
    int x=k-sum; if(x%2==0)//判断奇偶 { 
    cout<<n%d<<endl; } else { 
    cout<<d-n%d<<endl; } } return 0; } 

B 数三角形
思路：枚举，枚举每一个边，判断是否是相同，是否可以组成三角形，符合条件的三角形记录累加即可
AC代码：

讯享网#include<iostream> #include<cstdio> #include <stdio.h> #include<algorithm> #include<cstring> #include <string> #include<cmath> #include<cstdlib> #include<queue> #include<map> #include<vector> #include<bits/stdc++.h> #include <set> #define ll long long #define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #define inf 0x3f3f3f #define pi 3.98 using namespace std; const int N=2e5+10; const int mod=1e9+7; int a[120];//为防止越界适当开大一点数组 int main() { 
    int n; cin>>n; for(int i=0; i<n; i++) { 
    cin>>a[i]; } sort(a,a+n); ll sum=0; for(int i=0; i<n; i++) for(int j=i+1; j<n; j++) for(int k=j+1; k<n; k++) { 
    if(a[k]<a[j]+a[i]&&a[i]>a[k]-a[j]&&a[k]!=a[i]&&a[j]!=a[i]&&a[k]!=a[j])//判断是否符合条件 { 
    sum++; } } cout<<sum<<endl; return 0; } 

C 归零强迫症
思路：前缀和，用map（键值对进行存储），计算N个数的前缀和，并且用map进行存储相同前缀和的个数，
示例：如果1到5的前缀和为9，1到10的前缀和也为9，则代表5到10中间连续子序列的和一定为零，
所以根据找个条件可以进行解题
具体AC代码如下

#include<iostream> #include<cstdio> #include <stdio.h> #include<algorithm> #include<cstring> #include <string> #include<cmath> #include<cstdlib> #include<queue> #include<map> #include<vector> #include<bits/stdc++.h> #include <set> #define ll long long #define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #define inf 0x3f3f3f #define pi 3.98 using namespace std; const int N=2e5+10; const int mod=1e9+7; map<ll,ll> mp; int main() { 
    ll sum=0;//计算子序列数目 ll ans=0;//计算前缀和 int n; cin>>n; for(int i=0;i<n;i++) { 
    int x; cin>>x; ans+=x; if(ans==0) { 
    sum+=mp[ans]+1;//前缀和为0本身就可以组成 } else { 
    sum+=mp[ans];//前缀和不为零但前缀和相同的两两可以组成符合条件的连续子序列 } mp[ans]++; } cout<<sum<<endl; return 0; } 

D 幸运数字
/思路：
模拟题
朴素的方法是枚举三个字符仅有一个是数字的种类。
计算可知一共有3101026钟
然后遍历字符串。
总共复杂度为O(3101026N) 大概10的7次方
这种方法可在300ms内通过
*/

讯享网#include<bits/stdc++.h> typedef long long ll; using namespace std; char s[]; int main() { 
    int n; scanf("%d",&n); getchar(); for(int i=0;i<n;i++) scanf("%c",&s[i]); int ans=0; for(int i=0; i<26; i++) for(int j=0; j<10; j++) for(int k=0; k<10; k++) { 
    //字母+数字+数字 int t=0; for(int o=0; o<n; o++) { 
    if(s[o]==char('a'+i)&&t==0){ 
    t=1; continue;} if(s[o]==char('0'+j)&&t==1){ 
   t=2;continue;} if(s[o]==char('0'+k)&&t==2){ 
   t=3;break;} } if(t==3) ans++; //数字+字母+数字 t=0; for(int o=0; o<n ;o++) { 
    if(s[o]==char('0'+j)&&t==0){ 
    t=1; continue;} if(s[o]==char('a'+i)&&t==1){ 
   t=2;continue;} if(s[o]==char('0'+k)&&t==2){ 
   t=3;break;} } if(t==3) ans++; //数字+数字+字母 t=0; for(int o=0; o<n ;o++) { 
    if(s[o]==char('0'+j)&&t==0){ 
    t=1; continue;} if(s[o]==char('0'+k)&&t==1){ 
   t=2;continue;} if(s[o]==char('a'+i)&&t==2){ 
   t=3;break;} } if(t==3) ans++; } cout<<ans<<endl; return 0; } 

理解上面的思路后我们发现对于一个长度为1e5长度的字符。
如果前9000全是同一个字母‘a’,遍历的时候会做很多无用功。
上面的算法还可以优化。
26个字母+10个数字。一共36个字符。
那么你可以将每一个字符出现的位置按顺序保存起来。
比如aaa
那么q[‘1’]={1,2,3};q[‘2’]={4,5,6};q[‘a’]={7,8,9};
设nex[i][j]表示s串中第i后面第一个字符为j(0<j<160)的位置,也就是ASCll码对应的字符的位置。
规定s串的下标从1开始,如果不存在这样的位置则nex[i][j]=-1。
这样避免不必要的遍历。
时间复杂度比上一个算法少一个数量级。
30ms左右能过。
代码如下：

#include<bits/stdc++.h> using namespace std; int n,k,nex[][160]; char s[]; queue<int>q[160]; char v[10000][5]; int main() { 
    scanf("%d",&n); scanf("%s",s+1); for(int i=1;i<=n;i++) q[s[i]].push(i); for(int j=0;j<160;j++) { 
    if(!q[j].empty()) nex[0][j]=q[j].front(); else nex[0][j]=-1; } for(int i=1;i<=n;i++) { 
    q[s[i]].pop(); for(int j=0;j<160;j++) { 
    if(!q[j].empty()) nex[i][j]=q[j].front(); else nex[i][j]=-1; } } int cnt=0; for(int i=0; i<26; i++) for(int j=0; j<10; j++) for(int k=0; k<10; k++) { 
    v[cnt][1]=char('a'+i),v[cnt][2]=char('0'+j),v[cnt++][3]=char('0'+k); v[cnt][2]=char('a'+i),v[cnt][3]=char('0'+j),v[cnt++][1]=char('0'+k); v[cnt][3]=char('a'+i),v[cnt][1]=char('0'+j),v[cnt++][2]=char('0'+k); } int ans=0; for(int i=0;i<cnt;i++) { 
    int now=0; bool flag=true; for(int j=1;j<=3;j++) { 
    now=nex[now][v[i][j]]; if(now==-1) { 
    flag=false;break; } } if(flag) ans++; } cout<<ans<<endl; } 

讯享网#include<iostream> #include<cstdio> #include <stdio.h> #include<algorithm> #include<cstring> #include <string> #include<cmath> #include<cstdlib> #include<queue> #include<map> #include<vector> #include<bits/stdc++.h> #include <set> #define ll long long #define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #define inf 0x3f3f3f #define pi 3.98 using namespace std; const int N=1e6+10; const int mod=1e9+7; int dp[N]; int main() { 
    memset(dp,inf,sizeof(dp));//初始化为无穷大 dp[0]=0; for(ll i=0; i<=N; i++)//预处理所有情况 { 
    dp[i+1]=min(dp[i+1],dp[i]+1);//一块一块取的情况 for(ll j=6; i+j<=N; j*=6)//在已经取了i元的情况下按照6和6的次幂进行取钱 { 
    dp[i+j]=min(dp[i+j],dp[i]+1); } for(ll j=9; i+j<=N; j*=9)//在已经取了i元的情况下按照9和9的次幂进行取钱 { 
    dp[i+j]=min(dp[i+j],dp[i]+1); } } int n; cin>>n; cout<<dp[n]<<endl; return 0; } 

死板银行-进阶写法
上面的普通写法适用与数据较小的，如果N的范围扩大为1e16则DP写法将会超时，所以在此贴出进阶写法
先预处理出6的幂次和9的幂次，然后通过upper_bound函数（）查找到第一个大于N的6的次幂和9的次幂，-1即为最大的小于等于N的6的次幂和9的次幂
最后将6的次幂和9的次幂与N的差加起来比较选出最小的即为最后的值
具体执行情况观看下面的AC代码：

讯享网

#include<bits/stdc++.h> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int N=1e9+5; unordered_map<ll,int>f; vector<ll>v6,v9; int F(ll n) { 
    if(n==0||f[n]) return f[n]; f[n]=inf; int pos=upper_bound(v6.begin(),v6.end(),n)-v6.begin()-1;//找到第一个大于N的6的幂次，前一个即为最大的小于或等于N的6的幂次 if(pos>=0) f[n]=min(f[n],F(n-v6[pos])+1); pos=upper_bound(v9.begin(),v9.end(),n)-v9.begin()-1;//找到第一个大于N的9的幂次，前一个即为最大的小于或等于N的9的幂次 if(pos>=0) f[n]=min(f[n],F(n-v9[pos])+1);//取最小值 if(n<=5) f[n]=min(f[n],F(n-1)+1); return f[n]; } int main() { 
    for(ll x=6;x<=000000ll;x*=6) v6.push_back(x);//预处理6的幂次 for(ll x=9;x<=000000ll;x*=9) v9.push_back(x);//预处理9的幂次 int n;scanf("%d",&n); printf("%d\n",F(n)); } 

F 数因子

AC代码如下

讯享网#include <bits/stdc++.h> using namespace std; const int N=2e5+100; int mod=1e9+7; typedef long long ll; int main() { 
    ios::sync_with_stdio(0);cin.tie(0); int n;cin>>n; ll ans=0; for(int i=1;i<=n;i++){ 
    ans+=1ll*(i+n/i*i)*(n/i)/2; } cout<<ans<<endl; return 0; } 

G 欢乐挖宝记

///该题乍一看像01背包，但是体积很大使得我们不能开数组进行dp， 我们注意到n数值很小，所以我们可以暴力枚举哪些宝可以带哪些不能带
最后判断一下合法性即可。在这里介绍二进制枚举的方法。（关于二进制枚举大家可以百度学习一下）
AC代码如下：

#include <bits/stdc++.h> using namespace std; #define ll long long const int mod=1e9+7; const int N=2e5+100; ll n,V; ll v[100],w[100]; ll ansv,answ,ans; int main() { 
    ios::sync_with_stdio(0);cin.tie(0); cin>>n>>V; for(int i=1;i<=n;i++){ 
    cin>>v[i]>>w[i]; } for(int i=0;i<(1<<n);i++){ 
    ansv=0; answ=0; for(int j=0;j<n;j++){ 
    if(i&(1<<j)){ 
    ansv+=v[j+1]; answ+=w[j+1]; } if(ansv<=V) ans=max(ans,answ); } } cout<<ans<<endl; } 

对于字符串s，令t是s最长的前后缀，则：
若存在字符串c是t的前后缀，则t也是s的前后缀。
从而s的前后缀数量=t的前后缀数量+1

讯享网#include<bits/stdc++.h> using namespace std; const int N=5e5+5; int n,nex[N],ans[N]; char s[N]; int main() { 
    scanf("%d",&n); scanf("%s",s); nex[0]=-1; for(int i=0,k=-1;i<n;) { 
    if(k==-1||s[i]==s[k]) nex[++i]=++k; else k=nex[k]; } for(int i=1;i<=n;i++) ans[i]=ans[nex[i]]+1,printf(i==n?"%d\n":"%d ",ans[i]); }