思路：模拟
分析：
1 题目要求找到总共的电脑的消耗。题目明确指出在n个时间段之内电脑都是属于第一种状态，并且如果不是第一种状态只要移动鼠标或按键盘马上变为第一种状态。
2 题目还指出每一组输入都保证L<R，并且Ri-1<Li。那么我们只要每输入一个就处理一个即可。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n , p1 , p2 , p3 , t1 , t2;
int main(){
int sum;
int l , r , pre;
while(scanf("%d%d%d%d%d%d" , &n , &p1 , &p2 , &p3 , &t1 , &t2) != EOF){
scanf("%d%d" , &l , &r);
sum = (r-l)*p1;
pre = r;
for(int i = 1 ; i < n ; i++){
scanf("%d%d" , &l , &r);
sum += (r-l)*p1;
int dis = l-pre;
if(dis > t1){
sum += t1*p1;
dis -= t1;
if(dis > t2){
sum += t2*p2;
dis -= t2;
sum += dis*p3;
}
else
sum += dis*p2;
}
else
sum += dis*p1;
pre = r;/*记录前面一个位置*/
}
printf("%d\n" , sum);
}
return 0;
}
B
思路：简单的模拟题
分析：
1 题目给定n个可能的m值，然后要求对每一个m值输出相应的x , yl , yr；
2 xc 和 yc是这个矩形的最中心的位置，那么xc = (k+1)/2 ， yc = (k+1)/2。根据题目所给的公式进行模拟即可
3 n次模拟之间位置是不能重复使用的，所以这里应该使用一个vis[][]来标记当前点是否被坐了。
4 注意判断满足条件的时候要考虑数组越界的情况，看judge()函数
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 110
int n , k;
int xc , yc;
int vis[MAXN][MAXN];
bool judge(int x , int y , int m){
if(y+m-1 > k)/*如果不够直接返回false*/
return false;
for(int j = y ; j < y+m ; j++){
if(vis[x][j])
return false;
}
return true;
}
void solve(int m){
int min = 0x7FFFFFFF;
int x , yl , yr;
for(int i = 1 ; i <= k ; i++){
for(int j = 1 ; j <= k ; j++){
if(!vis[i][j]){
if(judge(i , j , m)){
int tmp = 0;
for(int t = j ; t < j+m ; t++){
tmp += abs(i-xc)+abs(t-yc);
}
if(tmp < min){
min = tmp;
x = i , yl = j , yr = j+m-1;
}
}
}
}
}
if(min == 0x7FFFFFFF)
printf("-1\n");
else{
printf("%d %d %d\n" , x , yl , yr);
for(int j = yl ; j <= yr ; j++)/*把x行从yl~yr标记为坐过*/
vis[x][j] = 1;
}
}
int main(){
int m;
while(scanf("%d%d" , &n , &k) != EOF){
memset(vis , 0 , sizeof(vis));
xc = (k+1)/2 , yc = (k+1)/2;
for(int i = 0 ; i < n ; i++){
scanf("%d" , &m);
solve(m);
}
}
return 0;
}
C
思路：数论
分析：
1 题目要求的是找到d(AB) = d(c) 并且AB != C的个数。比如n = 4的时候有 (3, 4, 3) and (4, 3, 3)两个。
2 根据题目的意思d(xy) = d(d(x)d(y))，那么d(AB)=d(d(A)d(B)) , 并d(AB) = d(C) , 所以d(C) = d(d(A)d(B)).假设现在x是[1,n]之间的数;
x = d(C)有num[d(C)]个，x = d(A)有num[d(A)]个，x = d(B)有num[d(B)]个。那么(A,B,C)的个数就是num[d(A)]*num[d(B)]*num[d(C)]。
3 树根
1 如果把一个大数的各位数字相加得到一个和，再把这个和的各位数字相加又得一个和，再继续作数字和，直到最后的数字和是个位数为止，这最后的数称为最初那个数的“数字根”。比如d(2345) = d(14) = d(5)，那么2345的数根就是5
2 一个数的数根就是它除以9的余数。d(x) = x%9 != 0 ? x%9 : 9；注意如果是x%9 = 0 , 那么数根为9.
4 [1,n]这个区间任意三个整数A ， B ， C，满足A*B = C的个数为(n/1+n/2+...+n/n)；
比如[1,4]，之间满足A*B = C的数
1*1 =1 , 1*2 = 2 , 1*3 = 3 , 1*4 = 5;
2*1 = 2 , 2*2 = 4;
3*1 = 3;
4*1 = 4;
总共8个 = 4/1+4/2+4/3+4/4
5 根据上面的知识求出所有的(A,B,C)-(A,B,C){AB=C}的即可。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 1000010
#define N 15
int n;
long long num[N];
/*求出每个数的数根*/
void init(){
memset(num , 0 , sizeof(num));
for(int i = 1 ; i <= n ; i++){
int tmp = i%9 != 0 ? i%9 : 9;
num[tmp]++;
}
}
int main(){
while(scanf("%d" , &n) != EOF){
init();
long long ans = 0;
for(int i = 1 ; i <= 9 ; i++){
for(int j = 1 ; j <= 9 ; j++){
int tmp = i*j;
tmp %= 9;
if(!tmp)
tmp = 9;
if(num[tmp])
ans += num[i]*num[j]*num[tmp];
}
}
for(int i = 1 ; i <= n ; i++)
ans -= n/i;
cout<<ans<<endl;
}
return 0;
}
D
思路：dp+lcis
分析：
1 定义状态dp[i][j]表示以a串的前i个字符b串的前j个字符且以b[j]为结尾构成的LCIS的长度
2 假设a[i] != b[j] , 那么dp[i][j] = dp[i-1][j];
假设a[i] = b[j] , 那么dp[i][j] = max{dp[i-1][k]}+1 ; 1<=k<=j-1
3 不难看到，这是一个时间复杂度为O(n^3)的DP，离平方还有一段距离。
但是，这个算法最关键的是，如果按照一个合理的递推顺序，max(dp[i-1][k])的值我们可以在之前访问dp[i][k]的时候通过维护更新一个 max变量得到。怎么得到呢？首先递推的顺序必须是状态的第一维在外层循环，第二维在内层循环。也就是算好了dp[1][len(b)]再去算dp[2] [1]。
如果按照这个递推顺序我们可以在每次外层循环的开始加上令一个max变量为0，然后开始内层循环。
当a[i]>b[j]的时候令max=dp[i-1][j]。如果循环到了a[i]==b[j]的时候，则令dp[i][j]=max+1。
最后答案是dp[len(a)][1]..dp[len(a)][len(b)]的最大值
代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
#define MAXN 510
int n , m;
int num1[MAXN] , num2[MAXN];
int dp[MAXN][MAXN];
int pre[MAXN];
/*递归输出*/
void output(int x){
if(pre[x] == -1){
printf("%d" , num2[x]);
return;
}
output(pre[x]);
printf(" %d" , num2[x]);
}
int DP(){
memset(dp , 0 , sizeof(dp));
memset(pre , -1 , sizeof(pre));
int max , k;
for(int i = 1 ; i <= n ; i++){
max = 0 ;
k = -1;
for(int j = 1 ; j <= m ; j++){
dp[i][j] = dp[i-1][j];
if(num1[i] > num2[j] && max < dp[i-1][j]){
max = dp[i-1][j];
k = j;
}
if(num1[i] == num2[j]){
dp[i][j] = max+1;
pre[j] = k;/*记录前驱*/
}
}
}
max = 0;
for(int i = 1 ; i <= m ; i++){
if(max < dp[n][i]){
max = dp[n][i];
k = i;
}
}
printf("%d\n" , max);
if(max)
output(k);
printf("\n");
}
int main(){
while(scanf("%d" , &n) != EOF){
for(int i = 1 ; i <= n ; i++)
scanf("%d" , &num1[i]);
scanf("%d" , &m);
for(int i = 1 ; i <= m ; i++)
scanf("%d" , &num2[i]);
DP();
}
return 0;
}
E
分析：
1 首先这是一道论文结论题。有一篇论文专门讨论了这个问题（其实CF上的题目描述和论文里的几乎一个字都没变，连举的例子都是一样的） 这篇论文题目是《APolynomial-timeAlgorithmfortheChange-MakingProblem》
2 其实我们可以感性的猜想出一个“看起来很靠谱”的算法：
•首先把所有货币从大到小排序。
•考虑某个大于w[i]但小于w[i−1]的数的表示方法。我们为了让正常人的贪心算法得到很差的解，应该让这个数恰好超过w[i]一点点，可以想象，必须让人贪心掉w[i]后发现剩下的数必须用一大陀小货币才能拼出。
•我们需要确定这个数S贪心掉w[i]后，到底会用多小的货币才能表示出来。于是我们找一个j，使得w[j+1]<S−w[i]<w[j]，作为贪心后最大可用货币。我们枚举这个j，找出利用i+1到j种货币能拼出的最大的严格小于w[i]的价格是多少，然后把这个值加上w[j]。
•我们检验所有这样的值，找到最小的一个即可。 这个做法直观感觉比较靠谱。事实上我们可以严格证明这个算法的正确性，但比较复杂，有兴趣可以自行参考论文。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n , ans , a[401];
int main(){
scanf("%d",&n);
for(int i = 1 ; i <= n ; i++)
scanf("%d", &a[i]);
ans = 1<<30;
for(int i = 2 ; i <= n ; i++){
for(int j = i ; j <= n ; j++){
int x = a[i-1]-1;
int y = 0;
for (int k = i ; k <= j ; k++){
y += x/a[k];
x %= a[k];
}
x = a[i-1]-1-x+a[j];
y++;
int x1 = x;
if(x1 < ans){
for(int k = 1 ; k <= n ; k++){
y -= x/a[k];
x %= a[k];
}
if(y < 0)
ans = x1;
}
}
}
if(ans == 1<<30)
puts("-1");
else
printf("%d\n",ans);
return 0;
}
