这次精神状态不怎么好，第一题的描述看得我就蛋疼。。。看完就速度写了~~~最终fst了%>_<%，第二题写复杂了，一直WA pretest 3，然后就紧张，导致精神更不好了，一直纠结在第二题，时间就这样过了，再一次拿了0蛋，妈蛋，真是蒟蒻啊%>_<%
A.看懂题之后就是A+B problem
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <map>
using namespace std;
int main()
{
int n,c;
cin>>n>>c;
int a,ans=0;
cin>>a;
for(int i=2;i<=n;i++)
{
int b;
cin>>b;
ans=max(ans,a-b-c);
a=b;
}
cout<<ans<<endl;
return 0;
}
B.给定字符串s = s1s2... s|s| ，问包含单词"bear"的子串有多少个？
假设当前字符串的长度为n,找到第一个"bear"所在的开始位置pos,那么符合要求的子串就有pos*(n-pos-2)个，之后把子串s1~spos删除
重复以上步骤，直至没有单词"bear"
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <map>
using namespace std;
#define MAXN 5555
string s;
int main()
{
cin>>s;
int ans=0,pos;
while((pos=s.find("bear"))!=-1)
{
ans+=(pos+1)*(s.size()-pos-3);
s.erase(s.begin(),s.begin()+pos+1);
}
cout<<ans<<endl;
return 0;
}
C.给定一个序列x[1],x[2],x[3],……x[n],然后接下来有m个查询，对于每个查询给出两个数l和r，要求你返回区间[l,r]内的每一个质数能够整除的序列元素个数的累加和
没有修改，只有查询，果断的离线~~~先用素数的线性筛法求出每个x[i]的最小质数因子，接下来对每个x[i]进行质因数分解，并对相应的因子进行统计，搞完之后再计算出前缀和出来(用sum数组表示)
，那么对于查询[l,r],结果就是sum[r]-sum[l-1]
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <map>
using namespace std;
#define MAXN 10000005
typedef long long LL;
int a[MAXN];
LL sum[MAXN];
int prime[MAXN],cnt=0;
int check[MAXN];
void get_prime()
{
memset(check,0,sizeof(check));
for(int i=2; i<MAXN; i++)
{
if(!check[i])
{
prime[cnt++]=i;
check[i]=i;
}
for(int j=0; j<cnt&&i*prime[j]<MAXN; j++)
{
check[i*prime[j]]=prime[j];
if(i%prime[j]==0) break;
}
}
}
void fac(int n)
{
for(int i=0; i<n; i++)
{
int d=a[i];
int pre=-1;
while(d!=1)
{
if(pre!=check[d])
sum[check[d]]++;
pre=check[d];
d/=check[d];
}
}
}
int main()
{
int n,m;
get_prime();
scanf("%d",&n);
for(int i=0; i<n; i++) scanf("%d",&a[i]);
fac(n);
for(int i=1; i<MAXN; i++) sum[i]+=sum[i-1];
scanf("%d",&m);
while(m--)
{
int l,r;
scanf("%d%d",&l,&r);
r=min(r,10000000);
if(l>r) printf("0\n");
else
printf("%I64d\n",sum[r]-sum[l-1]);
}
return 0;
}
D.略 计算几何全还给高中数学老师了。。。有时间得在好好学学
E.题目描述就不说了，就是给定几个变量的变化关系，问你在t次变化之后的值
根据题目意思可以求出各个变量的递推式来，由于t很大(t<1018)，所以线性模拟肯定超时，于是就要用到矩阵快速幂来加速递推(这学期刚好学了线代~~~)，构造出矩阵之后进行快速幂运算就OK
代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
const int maxn=6;
typedef long long LL;
typedef long long Matrix[maxn][maxn];
LL M[maxn][maxn]=
{
{2,1,1,0,1,0},
{1,2,0,1,1,0},
{1,1,1,0,1,0},
{1,1,0,1,1,0},
{0,0,0,0,1,1},
{0,0,0,0,0,1},
};
LL n;
void matrix_mul(Matrix A, Matrix B, Matrix res)
{
Matrix C;
memset(C, 0, sizeof(C));
for(int i = 0; i < 6; i++)
for(int j = 0; j < 6; j++)
for(int k = 0; k < 6; k++) C[i][j] = (C[i][j] + A[i][k] * B[k][j])%n;
memcpy(res, C, sizeof(C));
}
void matrix_pow(Matrix A,Matrix res,LL n)
{
Matrix a, r;
memcpy(a, A, sizeof(a));
memset(r, 0, sizeof(r));
for(int i = 0; i < 6; i++) r[i][i] = 1;
while(n)
{
if(n&1) matrix_mul(r, a, r);
n >>= 1;
matrix_mul(a, a, a);
}
memcpy(res, r, sizeof(r));
}
int main()
{
LL sx,sy,dx,dy,t;
Matrix A,B;
cin>>n>>sx>>sy>>dx>>dy>>t;
matrix_pow(M,A,t);
memset(B,0,sizeof(B));
B[0][0]=sx,B[1][0]=sy,B[2][0]=dx;
B[3][0]=dy,B[4][0]=0,B[5][0]=1;
matrix_mul(A,B,B);
LL x,y;
x=B[0][0],y=B[1][0];
if(x<=0) x+=n;
if(y<=0) y+=n;
cout<<x<<" "<<y<<endl;
return 0;
}