Codeforces

A,B,C：都很简单，不说了。 D：一棵树，给出树的结构，以及从树根到某个深度为偶数的节点的路径和，问能否构造一种所有节点点权和最小的树，输出最小点权和。 思路： 容易知道，如果想要点权和最小，那么尽可能让靠近树根的点承担更多的点权。

好久没玩cf了，竟然还能涨分（虽然我用的小号Orz) 三题，D应该是数学+DP…数学实在是忘干净了。。。 前面三题大体还好，都是1A，不过因为没有提前配置环境，耽误了一些时间。

题目链接：http://codeforces.com/contest/1015/problem/B 题意： 给出字符串s和字符串t，问一个将s变为t的策略。 可以做的变换为，交换s中相邻的字符串，该操作最多不能超过4000次，字符串长度最大为50.

比赛链接 10个月没写题了，菜啊。进行一点恢复性训练好了。 A: 给一个数，可以在填写若干（或者0）个前缀0，问能否变成回文数。 思路是直接删掉后面可能的出现的0再判断回文数就好。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2017年09月24日 星期日 13时51分06秒 4File Name :A.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define PB push_back 20#define fst first 21#define sec second 22#define lson l,m,rt<<1 23#define rson m+1,r,rt<<1|1 24#define ms(a,x) memset(a,x,sizeof(a)) 25typedef long long LL; 26#define pi pair < int ,int > 27#define MP make_pair 28 29using namespace std; 30const double eps = 1E-8; 31const int dx4[4]={1,0,0,-1}; 32const int dy4[4]={0,-1,1,0}; 33const int inf = 0x3f3f3f3f; 34bool check( int x) 35{ 36 vector<int>val; 37 while (x) 38 { 39 int tmp = x; 40 val.push_back(tmp); 41 x/=10; 42 } 43 int siz = val.size(); 44 if (siz==1) return true; 45 for ( int i = 0 ; i < siz/2 ; i++) 46 { 47 if (val[i]!=val[siz-1-i]) return false; 48 } 49 return true; 50} 51int main() 52{ 53 #ifndef ONLINE_JUDGE 54 //freopen("./in.txt","r",stdin); 55 #endif 56 int x; 57 cin>>x; 58 while(x==0) 59 { 60 x/=10; 61 } 62 if (check(x)) puts("YES"); 63 else puts("NO"); 64 65 66 #ifndef ONLINE_JUDGE 67 fclose(stdin); 68 #endif 69 return 0; 70} B: 2*n个人，每个人的重量为w[i]，要分成n-1组，每组2个人，以及2个单独的人。单独的人的不稳定性为0，每组的不稳定是该组的2个人的重量的差的绝对值。总的不稳定为所有组的不稳定性之和。问可能的最小不稳定性是多少。

http://codeforces.com/contest/740 A：现在有n个某种物品，要买k个使得n+k是4的倍数，可以的购买方案为a元1个，b元2个，c元3个，每种方案都可以买无限多。 思路：需要注意买多个未必比买少个贵..

题目链接 水题 乱搞。 1/* *********************************************** 2Author :111qqz 3Created Time :2016年03月30日 星期三 23时59分47秒 4File Name :code/cf/#346/A.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33int n,a,b; 34int main() 35{ 36 #ifndef ONLINE_JUDGE 37 freopen("code/in.txt","r",stdin); 38 #endif 39 cin>>n>>a>>b; 40 a = a + b; 41 while (a<=0) a+=n; 42 while (a>n) a-=n; 43 cout<<a<<endl; 44 45 #ifndef ONLINE_JUDGE 46 fclose(stdin); 47 #endif 48 return 0; 49}

比赛链接 两题QAQ A：7分钟1A 有n个大人m个小孩乘公交车，票价每人一元，一个大人最多免费带一个小孩，没有大人陪同的小孩不能乘车。 问是否有解，如果有解输出所有乘客付的钱的可能的最小值和可能的最大值。

题目链接 题意：给出n和k，给出一个长度为n的字符串表示房间的占用情况（0表示没占用，1表示已占用），从n个房间中找出k+1个，使得k+1中的k个距离k+1个中的1个的距离和最小。

http://codeforces.com/problemset/problem/519/C 题意：两种组队方式，3人一组，1个大牛+2个蒟蒻或者1个蒟蒻+2个大牛。给定大牛和蒟蒻的个数。问最多能组多少队。 思路：线性规划。设两种队分别有x,y个即可。 突然发现这题以前做过。。。比当时的代码简单了一些。还不错。

题意：求1+2+..+n的和。。但是对于是2的整数幂的项数。。符号是-。。 思路：可以先当做正数。(n+1)*n/2; 然后减去二倍的2的整数次幂的项的和。 坑点： 妈蛋第三次了。。。我想求小于等于n的最大是2的几次幂。。。取整的时候用int又会迷之错误。。。为什么说是迷之错误。。因为我WA的点的数据拿下来在本地跑是没有问题的。。。一交上去就错。。。不明觉厉。。。下次遇到double类型是数一点要小心小心再小心。。。第一次遇到是pow的返回类型是double，然后答案莫名奇妙的差1.第二次是#334 div2 的A题。。一道傻逼算分数的题我WA了一个小时。。。第三次是这个。。向下取整不要用（int）的强制转换。。而用floor吧。。233

题意：给定一个01串。要进行一次变换：选一段连续的非空的字串，将这段串的0和1反转（0变成1,1变成0） 然后问能得到的最长的0,1交替的序列的长度是多少（不一定连续）

题意是说，给定一个计算规则，求最终分数。 又傻逼了QAQ 遇到double类型一定要小心小心小心！ 虽然我觉得0.3*x一定是整数..这样子应该没问题的吧。。但还是跪了。下次有double型的数据即使是整数，可以这样写 int(x+0.5)

C. Day at the Beach time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output One day Squidward, Spongebob and Patrick decided to go to the beach. Unfortunately, the weather was bad, so the friends were unable to ride waves. However, they decided to spent their time building sand castles. At the end of the day there were n castles built by friends. Castles are numbered from 1 to n, and the height of the i-th castle is equal to h__i. When friends were about to leave, Squidward noticed, that castles are not ordered by their height, and this looks ugly. Now friends are going to reorder the castles in a way to obtain that condition h__i ≤ h__i + 1 holds for all i from 1 to n - 1.

B. Spongebob and Joke time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output While Patrick was gone shopping, Spongebob decided to play a little trick on his friend. The naughty Sponge browsed through Patrick’s personal stuff and found a sequence _a_1, _a_2, …, a__m of length m, consisting of integers from 1 to n, not necessarily distinct. Then he picked some sequence _f_1, _f_2, …, f__n of length n and for each number a__i got number b__i = f__a__i. To finish the prank he erased the initial sequence a__i.

1#include <cstdio> 2#include <iostream> 3#include <cmath> 4using namespace std; 5long long d1,d2,d3; 6int main() 7{ 8cin>>d1>>d2>>d3; 9long long ans = 999999999999; 10ans = min(ans,d1+d2+d3); 11ans = min (ans,d1*2+d2*2); 12ans = min (ans,d1*2+2*d3); 13ans = min(ans,d2*2+2*d3); 14cout<<ans<<endl; 15return 0; 16} time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Today Patrick waits for a visit from his friend Spongebob. To prepare for the visit, Patrick needs to buy some goodies in two stores located near his house. There is a _d_1 meter long road between his house and the first shop and a _d_2 meter long road between his house and the second shop. Also, there is a road of length _d_3 directly connecting these two shops to each other. Help Patrick calculate the minimum distance that he needs to walk in order to go to both shops and return to his house.

B - Layer Cake **Time Limit:**6000MS **Memory Limit:**524288KB 64bit IO Format:%I64d & %I64u Submit Status Practice CodeForces 589B Description Dasha decided to bake a big and tasty layer cake. In order to do that she went shopping and bought n rectangular cake layers. The length and the width of the i-th cake layer were a__i and b__i respectively, while the height of each cake layer was equal to one. From a cooking book Dasha learned that a cake must have a form of a rectangular parallelepiped constructed from cake layers of the same sizes.

A. Olesya and Rodion time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Olesya loves numbers consisting of n digits, and Rodion only likes numbers that are divisible by t. Find some number that satisfies both of them. Your task is: given the n and t print an integer strictly larger than zero consisting of n digits that is divisible by t. If such number doesn’t exist, print - 1. Input

As I work with students I often face the situation when if a problem doesn’t seem clear to a student at the first sight, it makes them unable to solve it. Indeed, you always hear about specific methods and techniques. But you don’t hear about how to think in order to apply them. In this note I’ll try to sum up my experience of solving programming contest problems. However, some pieces of advice will also be applicable for olympiads in mathematics and your first steps in academic research.