CF 385A. Bear and Raspberry
题目链接：
http://codeforces.com/problemset/problem/385/A
题目意思：
告诉物品每天的价格，如果在某天买，其后一天卖，在租金为c的情况下能获得的最大利润。
解题思路：
直接暴力枚举就行了，水题。注意答案为负的情况下，应输出0.
代码：
//#include<CSpreadSheet.h>
#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll __int64
#define LL long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#define M 1000000007
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
int save[1100];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n,c;
while(~scanf("%d%d",&n,&c))
{
int cur;
int ans=0;
for(int i=1;i<=n;i++)
scanf("%d",&save[i]);
for(int i=1;i<n;i++)
{
ans=max(ans,save[i]-save[i+1]-c);
}
printf("%d\n",ans);
}
return 0;
}
CF 385B. Bear and Strings题目链接：
http://codeforces.com/contest/385/problem/B
题目意思：
给一个字符串，求包含"bear"的子串的个数。
解题思路：
分类计数。先标记出现bear的各个位置，扫描每个bear,统计距上一个bear之间的字母个数n和该bear后面的总的字母个数m，加上n*m.直到处理完所有的bear为止。
代码：
//#include<CSpreadSheet.h>
#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll __int64
#define LL long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#define M 1000000007
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
#define Maxn 5500
char save[Maxn];
ll n;
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(~scanf("%s",save+1))
{
n=strlen(save+1);
ll ans=0;
ll la=0;
for(ll i=1;i<=n-3;i++)
{
if(strncmp(save+i,"bear",4)==0)
{
ans+=(i-la)*(n-(i+3)+1); //i-la表示距离上一个bear之间的字母的个数
//printf("%d\n")
la=i;
}
}
printf("%I64d\n",ans);
}
return 0;
}
CF 385C. Bear and Prime Numbers
题目链接：
http://codeforces.com/contest/385/problem/C
题目意思：
给n(n<=10^6)个数xi(xi<=10^7),有m个区间，求每个区间内的质数集合能整除n个数中数的个数的总和。
解题思路：
暴力。先素数筛选法（o(nlgn))求出10^7内的质数.然后反过来思考，对每个xi,分解质因数，对每个质因数计数+1.
dp[i]表示1~i内的质数能整除xi的个数和。o(1)输出答案。
代码：
//#include<CSpreadSheet.h>
#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll __int64
#define LL long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#define M 1000000007
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
#define Maxn 1100000
#define Max 10000000
int pri[Maxn];
bool prime[Max+10];
int num[Max+10],dp[Max+10],n,cnt;
void init() //素数筛选法
{
cnt=0;
memset(prime,true,sizeof(prime));
for(int i=2;i<=Max;i++)
{
if(prime[i])
{
pri[++cnt]=i;
for(int j=i*2;j<=Max;j+=i)
if(prime[j])
prime[j]=false;
}
}
// printf("%d\n",cnt);
}
void Cal(int cur) //num[i]表示质数i能整除xi的个数
{
if(prime[cur])
{
num[cur]++;
return ;
}
for(int i=1;i<=cnt&&pri[i]<=cur;i++)
{
if(cur%pri[i]==0)
{
num[pri[i]]++;
while(cur%pri[i]==0)
cur/=pri[i];
if(cur!=1)
{
if(prime[cur])
{
num[cur]++;
return ;
}
}
else
return ;
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
init();
while(~scanf("%d",&n))
{
int cur;
memset(num,0,sizeof(num));
for(int i=1;i<=n;i++)
{
scanf("%d",&cur);
Cal(cur);
}
dp[0]=0;
for(int i=1;i<=Max;i++)
{
dp[i]=num[i]+dp[i-1];
}
int m;
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
ll l,r;
scanf("%I64d%I64d",&l,&r);
if(l>Max)
l=Max;
if(r>Max)
r=Max;
printf("%d\n",dp[r]-dp[l-1]);
}
}
return 0;
}
CF 385E. Bear in the Field
题目链接：
http://codeforces.com/contest/385/problem/E
题目意思：
在一个n*n的棋盘上，开始在位置sx,sy,开始速度为dx,dy.，开始每个格子的草莓数为格子的横纵坐标之和，每经过一秒顺序发生：1、速度增加当前格子的草莓数，2、位置增加速度单位（超出的部分模n) 3、每个格子的草莓数增加一个。求经过t秒后所在的位置。
解题思路：
记ftx为t秒后位置的横坐标，fty为纵坐标，dtx为t秒后的横坐标速度，dty为纵坐标速度。由题意可列出递推方程。
1、ftx=ft-1x+dtx
2、fty=ft-1y+dty
3、dtx=dt-1x+ft-1x+ft-1y+t-1+2 （注意此时的ftx、fty从0开始计数）
4、dty=dt-1y+ft-1x+ft-1y+t-1+2
将3和4式带入1、2中得：
ftx=2ft-1x+ft-1y+dt-1x+t+1
fty=2ft-1y+ft-1x+dt-1y+t+1
所以建立转移矩阵得：
2 1 1 0 1 2 ft-1x ftx
1 2 0 1 1 2 ft-1y fty
1 1 1 0 1 2 dt-1x = dtx
1 1 0 1 1 2 dt-1y dty
0 0 0 0 1 1 t-1 t
0 0 0 0 0 1 1 1
直接快速幂，最后可得出答案。
代码：
//#include<CSpreadSheet.h>
#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll __int64
#define LL long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#define M 1000000007
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
#define Maxn 10
ll n,t;
ll sx,sy,dx,dy;
struct Mar
{
int row,col;
ll s[Maxn][Maxn];;
void init(int a,int b)
{
row=a,col=b;
memset(s,0,sizeof(s));
}
};
Mar operator * (const Mar & a,const Mar & b)
{
Mar res;
res.init(a.row,b.col);
for(int k=1;k<=a.col;k++)
{
for(int i=1;i<=res.row;i++)
{
if(a.s[i][k]==0)
continue;
for(int j=1;j<=res.col;j++)
{
if(b.s[k][j]==0)
continue;
res.s[i][j]=((a.s[i][k]*b.s[k][j]+res.s[i][j])%n+n)%n;
}
}
}
return res;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(~scanf("%I64d%I64d%I64d%I64d%I64d%I64d",&n,&sx,&sy,&dx,&dy,&t))
{
Mar ans;
ans.init(6,1);
ans.s[1][1]=sx-1;
ans.s[2][1]=sy-1;
ans.s[3][1]=dx;
ans.s[4][1]=dy;
ans.s[5][1]=0;
ans.s[6][1]=1;
Mar ba; //基矩阵
ba.init(6,6);
ba.s[1][1]=2;
ba.s[1][2]=1;
ba.s[1][3]=1;
ba.s[1][5]=1;
ba.s[1][6]=2;
ba.s[2][1]=1;
ba.s[2][2]=2;
ba.s[2][4]=1;
ba.s[2][5]=1;
ba.s[2][6]=2;
ba.s[3][1]=1;
ba.s[3][2]=1;
ba.s[3][3]=1;
ba.s[3][5]=1;
ba.s[3][6]=2;
ba.s[4][1]=1;
ba.s[4][2]=1;
ba.s[4][4]=1;
ba.s[4][5]=1;
ba.s[4][6]=2;
ba.s[5][5]=1;
ba.s[5][6]=1;
ba.s[6][6]=1;
while(t) //快速幂
{
if(t&1)
ans=ba*ans;
ba=ba*ba;
t>>=1;
}
printf("%I64d %I64d\n",ans.s[1][1]+1,ans.s[2][1]+1);
}
return 0;
}
memory limit per test
256 megabytes