点击打开链接cf#10
A
思路:模拟
分析:
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;
}
分享到:
相关推荐
Codeforces Round #723 (Div. 2).md
Codeforces global round 10 codes
E. Cyclic Components 题目链接-E. Cyclic Components 题目大意 给你nnn个点和mmm条边,求所构成图中单圈环的个数 ...并查集并查集并查集 很明显单圈环每个点的度都为222,所以我们可以用数组cnt[]记录每个点的度,...
传送门 题意: 开始位置在0,问能否跳到n+1位置 每步只能跳d 在1——n每个位置有方向,L,R,求d的最小值 思路: 只用找相邻两个R之间的最大值即可 代码: #include #include ...typedef long long l
传送门 题意: 给一个数k,构造一个矩阵 用上面那个代码跑出来的值dp[n][m],和找到一个走法,从(1,1)走到(n,m)路径上的值相与的最大值ans,他们的差值是k 思路: 构造一个2*3的就可以了 ...
传送门 题意: 一个长度为n的数组,为删除一些数后,剩下的数能否构成长度大于3的回文数组 思路: 只要能找到两个相等的数,且他们的间距大于2即可 o(n^2)的暴力就能过 比赛时写了一个o(n)的 就是把所有相等的数放到...
B. K-th Beautiful String 题目链接-B. K-th Beautiful String 题目大意 长度为n的字符串包含n−2n−2n−2个aaa和222个bbb,求按照字典序排列输出第kkk个字符串 解题思路 第一个bbb在倒数第二位有1个字符串,在...
Codeforces Round #629 (Div. 3) E.Tree Queries (DFS) 思路:若ai 在路径上 ,则ai的父结点一定在路径上,若ai是路径上某个结点的子结点,则ai的父结点一定在路径上,综上只需考虑ai的父节点就行了。对每个ai判断...
Codeforces round 678 division 2 codes
C. Ehab and Path-etic MEXs 题意 给两两节点放一个数字(0~n-2 唯一) 给你一棵树,求所有任意两节点相连的路以外的路上的数字的最小值最小 思路 构造 若一个点连了三条边及以上,则这个点的边从最小值开始赋值。...
传送门 题意: 给一个长度为n的数组,两种操作,一个是把任意一个ai变成ai+2a_i变成a_i+2ai变成ai+2,另一个是如果所有数都大于0,可以把所有数减1,问通过这些操作能否把所有数变为0 思路: ...
Codeforces round 678 D2_Codeforces_源码
B. Longest Palindrome time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Returning back to problem solving, Gildong is now studying about ...
惭愧,前几天刚学的dfs序判祖先关系都忘了用。。 这题我们先把所有点都变成父亲节点(根节点不变),这样只需要判所有节点是否在一条链上。 由于判断x是y的祖先:需要满足:st[x]<=st[y]<...
A #include using namespace std; typedef long long ll; int main(){ int t; cin>>t; while(t--){ ll x; cin>>x; cout<<1>>t; while(t--){ st.clear(); ll n; cin >>n;... ll re
题目传送 题目大意: 定义一个函数:f(x,y) = (x|y)-y 将数组排序,使得最后结果最大。 分析: 手写几组数据后发现,最后的结果只和第一个数字有关,也就是只需要确定第一个...const int maxn = 1e5 + 10; int an[maxn
A. EhAb AnD gCd 题目链接-A. EhAb AnD gCd 题目大意 输入一个正整数x,找出这样的2个正整数a和b,使得gcd(a,b)+lcm(a,b)=x 解题思路 找最特殊的情况a=1,b=x-1即可 这样a,b两个数最大公因数为1,最小公倍数x-1,...
传送门 A. EhAb AnD gCd 直接输出1,n-1即可 #include #include #include #include #include #include #include #include #include #include #define pb push_back #define lb lower_bound ...con
传说门 刚好今晚是中国场! 其实这道题比较水,但当时思路错,一心想着化简公式,浪费了好多时间a.a 题意:三个数组,求(x-y)(x-y)+(x-z)(x-z)+(y-z)*(y-z)的最小值 题解:6nlogn,先sort三个数组a,b,c, 六次枚举二...