ACM

D. Three Logos time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Three companies decided to order a billboard with pictures of their logos. A billboard is a big square board. A logo of each company is a rectangle of a non-zero area. Advertisers will put up the ad only if it is possible to place all three logos on the billboard so that they do not overlap and the billboard has no empty space left. When you put a logo on the billboard, you should rotate it so that the sides were parallel to the sides of the billboard.

Desiderium # **Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 427 Accepted Submission(s): 167 ** Problem Description There is a set of intervals, the size of this set is n. If we select a subset of this set with equal probability, how many the expected length of intervals’ union of this subset is? We assume that the length of empty set’s union is 0, and we want the answer multiply 2n modulo 109+7.

time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Petya loves computer games. Finally a game that he’s been waiting for so long came out! The main character of this game has n different skills, each of which is characterized by an integer a__i from 0 to 100. The higher the number_a__i_ is, the higher is the i-th skill of the character. The total rating of the character is calculated as the sum of the values of for all i from 1 to n. The expression ⌊ x⌋ denotes the result of rounding the number x down to the nearest integer.

B. Luxurious Houses time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output The capital of Berland has n multifloor buildings. The architect who built up the capital was very creative, so all the houses were built in one row. Let’s enumerate all the houses from left to right, starting with one. A house is considered to be luxurious if the number of floors in it is strictly greater than in all the houses with larger numbers. In other words, a house is luxurious if the number of floors in it is strictly greater than in all the houses, which are located to the right from it. In this task it is assumed that the heights of floors in the houses are the same.

A. Vasya the Hipster time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output One day Vasya the Hipster decided to count how many socks he had. It turned out that he had a red socks and b blue socks. According to the latest fashion, hipsters should wear the socks of different colors: a red one on the left foot, a blue one on the right foot. Every day Vasya puts on new socks in the morning and throws them away before going to bed as he doesn’t want to wash them.

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.

In ``Hangman Judge,’’ you are to write a program that judges a series of Hangman games. For each game, the answer to the puzzle is given as well as the guesses. Rules are the same as the classic game of hangman, and are given as follows: 1. The contestant tries to solve to puzzle by guessing one letter at a time. 2. Every time a guess is correct, all the characters in the word that match the guess will be ``turned over.'' For example, if your guess is ``o'' and the word is ``book'', then both ``o''s in the solution will be counted as ``solved.'' 3. Every time a wrong guess is made, a stroke will be added to the drawing of a hangman, which needs 7 strokes to complete. Each unique wrong guess only counts against the contestant once. ______ | | | O | /| | | | / __|_ | |______ |_________| 4. If the drawing of the hangman is completed before the contestant has successfully guessed all the characters of the word, the contestant loses. 5. If the contestant has guessed all the characters of the word before the drawing is complete, the contestant wins the game. 6. If the contestant does not guess enough letters to either win or lose, the contestant chickens out. Your task as the ``Hangman Judge’’ is to determine, for each game, whether the contestant wins, loses, or fails to finish a game.

模拟． 直接搞… 并不明白坑在哪里．．． 排在我前面被hack了１００多人… 代码实现 1/************************************************************************* 2 > File Name: code/bc/#57/1001.cpp 3 > Author: 111qqz 4 > Email: rkz2013@126.com 5 > Created Time: 2015年09月26日 星期六 19时04分34秒 6 ************************************************************************/ 7 8#include<iostream> 9#include<iomanip> 10#include<cstdio> 11#include<algorithm> 12#include<cmath> 13#include<cstring> 14#include<string> 15#include<map> 16#include<set> 17#include<queue> 18#include<vector> 19#include<stack> 20#include<cctype> 21#define y1 hust111qqz 22#define yn hez111qqz 23#define j1 cute111qqz 24#define ms(a,x) memset(a,x,sizeof(a)) 25#define lr dying111qqz 26using namespace std; 27#define For(i, n) for (int i=0;i<int(n);++i) 28typedef long long LL; 29typedef double DB; 30const int inf = 0x3f3f3f3f; 31const int N=1E3+7; 32char str[N]; 33int len; 34int main() 35{ 36 #ifndef ONLINE_JUDGE 37 freopen("in.txt","r",stdin); 38 #endif 39 int T; 40 cin>>T; 41 while (T--) 42 { 43 scanf("%s",str); 44 len = strlen(str); 45 int cnt = 0; 46 int ans = 0 ; 47 for ( int i = 0 ; i < len ; i++) 48 { 49 if (str[i]=='(') 50 { 51 cnt++; 52 } 53 else 54 { 55 cnt--; 56 if (cnt>=0) 57 { 58 ans++; 59 } 60 if (cnt<0) 61 cnt = 0 ; 62 } 63 } 64 printf("%d\n",ans); 65 } 66 67 #ifndef ONLINE_JUDGE 68 fclose(stdin); 69 #endif 70 return 0; 71}

比较水． 唯一一点需要注意的是… 可能有重复元素… 因为我的思路是用两棵一维树状数组搞.. 每个点标记为1 然后看矩形的两个方向中是否至少有一个方向上和等于长度…

B. Kefa and Company time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Kefa wants to celebrate his first big salary by going to restaurant. However, he needs company. Kefa has n friends, each friend will agree to go to the restaurant if Kefa asks. Each friend is characterized by the amount of money he has and the friendship factor in respect to Kefa. The parrot doesn’t want any friend to feel poor compared to somebody else in the company (Kefa doesn’t count). A friend feels poor if in the company there is someone who has at least d units of money more than he does. Also, Kefa wants the total friendship factor of the members of the company to be maximum. Help him invite an optimal company!

一开始迷之wa… 先找出素数下标的上界就可以A… 然后纠结了２０分钟．．． 然后发现是预处理的素数少了一个素数．． 我预处理是处理到＜１０００５的素数．．． 最大数１００００，而超过１００００的第一个素数是１０００７ 这样判断终止条件就会死循环… sad

不多说，直接代码。 代码实现 1/************************************************************************* 2 > File Name: code/poj/2100.cpp 3 > Author: 111qqz 4 > Email: rkz2013@126.com 5 > Created Time: 2015年09月25日 星期五 00时42分49秒 6 ************************************************************************/ 7 8#include<iostream> 9#include<iomanip> 10#include<cstdio> 11#include<algorithm> 12#include<cmath> 13#include<cstring> 14#include<string> 15#include<map> 16#include<set> 17#include<queue> 18#include<vector> 19#include<stack> 20#include<cctype> 21#define y1 hust111qqz 22#define yn hez111qqz 23#define j1 cute111qqz 24#define ms(a,x) memset(a,x,sizeof(a)) 25#define lr dying111qqz 26using namespace std; 27#define For(i, n) for (int i=0;i<int(n);++i) 28typedef long long LL; 29typedef double DB; 30const int inf = 0x3f3f3f3f; 31LL n; 32LL maxn; 33vector<LL>ans; 34 35 36void solve() 37{ 38 LL head = 1,tail = 1; 39 LL sum = 0 ; 40 41 while (tail<=maxn) 42 { 43 sum = sum + tail*tail; 44 45 if (sum>=n) 46 { 47 while (sum>n)//主要是while，因为可能要减掉多个才能小于n 48 { 49 sum -= head*head; 50 head++; 51 } 52 if (sum==n) 53 {//因为要先输出答案个数...所以必须存起来延迟输出... 54 ans.push_back(head); 55 ans.push_back(tail); 56 } 57 } 58 tail++; 59 } 60 LL sz = ans.size(); 61 printf("%lld\n",sz/2); 62 for (LL i = 0 ; i<ans.size() ; i = i +2) 63 { 64 printf("%lld",ans[i+1]-ans[i]+1); 65 for ( LL j = ans[i] ; j <=ans[i+1] ; j++) printf(" %lld",j); 66 printf("\n"); 67 } 68 69} 70int main() 71{ 72 #ifndef ONLINE_JUDGE 73 freopen("in.txt","r",stdin); 74 #endif 75 scanf("%lld",&n); 76 maxn = ceil(sqrt(n)); 77 solve(); 78 79 #ifndef ONLINE_JUDGE 80 fclose(stdin); 81 #endif 82 return 0; 83}

题意　：给定一个长度为n的区间．然后给k次询问，每次一个数t，求一个区间[l,r]使得这个区间和的绝对值最接近t 没办法直接尺取. 先预处理出来前缀和 如果要找一对区间的和的绝对值最最近t

Jessica’s Reading Problem Time Limit Memory Limit Total Submissions Accepted 1000MS 65536K 8787 2824 Description Jessica’s a very lovely girl wooed by lots of boys. Recently she has a problem. The final exam is coming, yet she has spent little time on it. If she wants to pass it, she has to master all ideas included in a very thick text book. The author of that text book, like other authors, is extremely fussy about the ideas, thus some ideas are covered more than once. Jessica think if she managed to read each idea at least once, she can pass the exam. She decides to read only one contiguous part of the book which contains all ideas covered by the entire book. And of course, the sub-book should be as thin as possible.