Brute Force

题目链接 题意： # 给出由小写字母，’?‘和’*‘组成的字符串s，仅由小写字母组成的字符串t，问按照规则s能否变成t.

题目链接 题意：求一棵二叉树中，所有一段连续路径之和等于给定值的路径数目。 思路：想了半天就只能想到暴力。。。复杂度大概O(n^2)。。。也不是不可以接受。。。但是感觉这也太暴力了。。就去看了题解。。。发现题解就还真是暴力orz。。。

题目链接 题意：一段数字串，如果一个数字k满足，将该串分成若干个长度为K的子串，这些子串两两满足每个字符出现的次数一样多，那么称为k是一个阿贝尔周期。现在问所有合法的阿贝尔周期。

题目链接 题意：n个数围成一圈，对于负数可以进行magic操作，也就是取反，但是会影响到左右相邻的，加上这个负数。问最少进行多少次magic操作，使得所有数都是非负。 思路：我们知道，如果一个负数想变成整数的话，只能通过magic 操作。唯一可能影响次数的就是顺序。

题目链接 题意：n个城市，m条双向路，要从k条中选择一个，使得到其他n-k个城市中的某个城市的距离最短。 思路：直接暴力 枚举。1A 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月20日 星期六 21时02分14秒 4File Name :code/cf/#368/B.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <set> 13#include <deque> 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 27using namespace std; 28const double eps = 1E-8; 29const int dx4[4]={1,0,0,-1}; 30const int dy4[4]={0,-1,1,0}; 31const int inf = 0x3f3f3f3f; 32const int N =1E5+7; 33int n,m,k; 34vector <pair <int,LL> >edge[N]; 35int b[N]; 36bool cangku[N]; 37int main() 38{ 39 #ifndef ONLINE_JUDGE 40 freopen("code/in.txt","r",stdin); 41 #endif 42 ios::sync_with_stdio(false); 43 cin>>n>>m>>k; 44 ms(cangku,false); 45 for ( int i = 1 ; i <= m ; i++) 46 { 47 int u,v; 48 LL w; 49 cin>>u>>v>>w; 50 edge[u].push_back(make_pair(v,w)); 51 edge[v].push_back(make_pair(u,w)); 52 } 53 if (k==0) 54 { 55 cout<<-1<<endl; 56 return 0 ; 57 } 58 for ( int i = 1 ; i <= k ; i++) 59 { 60 cin>>b[i]; 61 cangku[b[i]] = true; 62 } 63 if (k==n) 64 { 65 cout<<-1<<endl; 66 return 0; 67 } 68 LL ans = inf; 69 for (int i = 1 ; i <= k ; i++) 70 { 71 int u = b[i]; 72 int siz = edge[u].size(); 73 for (int j = 0 ; j < siz ; j++) 74 { 75 int v = edge[u][j].fst; 76 if (cangku[v]) continue; 77 LL w = edge[u][j].sec; 78 ans = min(ans,w); 79 } 80 } 81 if (ans==inf) ans = -1; 82 cout<<ans<<endl; 83 #ifndef ONLINE_JUDGE 84 fclose(stdin); 85 #endif 86 return 0; 87}

题目链接 。。。这题也能成hack题。。。。有毒啊。。然后我room里所有人都写对了。。。是我看这道题看得太早了？ 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月20日 星期六 21时01分57秒 4File Name :code/cf/#368/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 <deque> 15#include <map> 16#include <string> 17#include <cmath> 18#include <cstdlib> 19#include <ctime> 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; 34const int N=105; 35int n,m; 36int main() 37{ 38 #ifndef ONLINE_JUDGE 39 freopen("code/in.txt","r",stdin); 40 #endif 41 42 cin>>n>>m; 43 bool ok = false; 44 for ( int i = 1 ; i <= n ; i++) 45 for ( int j = 1 ; j <=m ; j++ ) 46 { 47 char col; 48 cin>>col; 49 if (col=='C'||col=='M'||col=='Y') ok = true; 50 } 51 if (ok) cout<<"#Color"<<endl; 52 else cout<<"#Black&White"<<endl; 53 54 #ifndef ONLINE_JUDGE 55 fclose(stdin); 56 #endif 57 return 0; 58}

cf689C 题意：给出一个m。。问恰好使得不超过某个n的a*b^3（a,b是正整数）的方案数为m的n是多少。。。 思路：暴力+二分。。。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年07月18日 星期一 15时58分55秒 4File Name :code/2016whust/G.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; 33LL m,n; 34LL ans; 35LL cal( LL x) 36{ 37 LL res = 0LL; 38 for ( LL i =2 ; i * i * i <= x ; i++) 39 res+=x/(i*i*i); 40 return res; 41} 42int main() 43{ 44 #ifndef ONLINE_JUDGE 45 freopen("code/in.txt","r",stdin); 46 #endif 47 48 cin>>m; 49 n = 0 ; 50 51 LL cur = 1LL<<60; 52// cout<<"cur:"<<cur<<endl; 53 while (cur!=0LL) 54 { 55 LL tmp = cal(n+cur); 56 if (tmp<m) n +=cur; 57 58 cur >>=1LL; 59 } 60 n++; 61// cout<<" n:"<<n<<endl; 62 if (cal(n)!=m) ans = -1; 63 else ans = n; 64 65 cout<<ans<<endl; 66 67 68 #ifndef ONLINE_JUDGE 69 fclose(stdin); 70 #endif 71 return 0; 72}

poj 3368 题目链接 题意：给出n个非减的数a[i]，求区间[l,r]中出现次数最多的数的出现的次数。 思路：由于数列非减，那么相等的数一定相邻。很容易系哪个到构造另一个数组f[i]，表示从当前位置向左边延伸最多延伸几个相等的数。

hdu3183题目链接 题意：n位长的数字串（n<=1000)，删掉m个（m<=n），使得剩下的数字串表示的数字最小。 忽略前导0. 思路：暴力搞就可以。要注意每位数字是有一定位置的范围的。比如当前是第i位数字，后面还要取n-m-i位数字，那么第i位数字最多只能取到第k位，k=m+i，因为这样才能保证后面还有n-m-i位数字。

1653: [Usaco2006 Feb]Backward Digit Sums # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 349 Solved: 258 [Submit][Status][Discuss] Description # FJ and his cows enjoy playing a mental game. They write down the numbers from 1 to N (1 <= N <= 10) in a certain order and then sum adjacent numbers to produce a new list with one fewer number. They repeat this until only a single number is left. For example, one instance of the game (when N=4) might go like this: 3 1 2 4 4 3 6 7 9 16 Behind FJ’s back, the cows have started playing a more difficult game, in which they try to determine the starting sequence from only the final total and the number N. Unfortunately, the game is a bit above FJ’s mental arithmetic capabilities. Write a program to help FJ play the game and keep up with the cows.

1622: [Usaco2008 Open]Word Power 名字的能量 # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 462 Solved: 228 [Submit][Status][Discuss] Description # 约翰想要计算他那N(1≤N≤1000)只奶牛的名字的能量．每只奶牛的名字由不超过1000个字待构成，没有一个名字是空字体串， 约翰有一张“能量字符串表”，上面有M(1≤M≤100)个代表能量的字符串．每个字符串由不超过30个字体构成，同样不存在空字符串．一个奶牛的名字蕴含多少个能量字符串，这个名字就有多少能量．所谓“蕴含”，是指某个能量字符串的所有字符都在名字串中按顺序出现（不一定一个紧接着一个）． 所有的大写字母和小写字母都是等价的．比如，在贝茜的名字“Bessie”里，蕴含有“Be” “sI”“EE”以及“Es”等等字符串，但不蕴含“lS”或“eB”．请帮约翰计算他的奶牛的名字的能量．

1599: [Usaco2008 Oct]笨重的石子 # Time Limit: 10 Sec Memory Limit: 162 MB Submit: 886 Solved: 614 [Submit][Status][Discuss] Description # 贝西喜欢棋盘游戏和角色扮演类游戏所以她说服Farmer John把她带到玩具店，在那里，她购买了三个不同的骰子，这三个质量均匀的骰子，分别有S1,S2,S3个面。(2 <= S1 <= 20; 2 <= S2 <= 20; 2 <= S3 <= 40). 贝西掷啊掷啊掷啊，想要知道出现几率最大的和是多少。 问题给出三个骰子的面数，让你求出出现几率最大的和是多少。如果有很多种和出现的几率相同，那么就输出小的那一个。

题目链接 题意：有1E9个礼物，第i个礼物价钱是i，然后现在已经有n个不重复的礼物，a[i],m元钱，想尽可能多得买不同种类的礼物，还能买多少个。 思路：先不考虑已经买的，从1连续买到k，然后考虑在这个区间内已经买的，等于实际上没有花钱。 反正就是暴力搞啊搞啊。。我也不知道怎么搞。。 结果最后。。方案数为0的时候。。。最后一个答案我是单独输出的。。忘了判断了。。。所以会输出两个0.宝宝心里苦啊。。。。。。。。

题目链接 题意：给出8个点，问能否构成一个8元素集合，使得x1/* *********************************************** Author :111qqz Created Time :2016年03月31日 星期四 13时39分27秒 File Name :code/cf/problem/334B.cpp ************************************************ */ #include #include #include #include #include #include #include #include #include #include #include #include #define fst first #define sec second #define lson l,m,rt«1 #define rson m+1,r,rt«1|1 #define ms(a,x) memset(a,x,sizeof(a)) typedef long long LL; #define pi pair < int ,int > #define MP make_pair

题目链接 题意：2×2的格子，有三个位置分别放”A“ “B” “C” ，一个位置为空。只有和空位相邻位置上的字母能移动到空位。没有其他移动规则。现在给出两个状态。问能否互相转化。 思路： 貌似可以dfs…？但是一共才2*2，可以直接暴力枚举。 手写一种变换最多能有12种。

题目链接 题意：给出一个数列，按照最好的策略排序使得a[i+1]>a[i]的对数尽可能多，问最多的对数是多少。 思路：类似计数排序？ 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年03月07日 星期一 17时06分48秒 4File Name :code/cf/#345/B.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; 33const int N=1E3+7; 34int n ; 35int a[N]; 36int cnt[N]; 37int num[N]; 38int sum[N]; 39int main() 40{ 41 #ifndef ONLINE_JUDGE 42 freopen("code/in.txt","r",stdin); 43 #endif 44 45 cin>>n; 46 ms(cnt,0); 47 ms(num,0); 48 ms(sum,0); 49 for ( int i = 1 ; i <= n ; i++) 50 { 51 cin>>a[i]; 52 cnt[a[i]]++; 53 } 54 if (n==1) 55 { 56 puts("0"); 57 return 0 ; 58 } 59 if (n==2) 60 { 61 if (a[1]==a[2]) 62 { 63 puts("0"); 64 } 65 else 66 { 67 puts("1"); 68 } 69 return 0; 70 } 71 72 int mx = -1; 73 for ( int i = 1 ; i <= 1000 ; i++) 74 { 75 num[cnt[i]]++; 76 mx = max(mx,cnt[i]); 77 } 78 79 for ( int i = mx ; i >= 1 ; i --) 80 { 81 sum[i] = sum[i+1]+num[i]; 82 } 83 84 int ans = 0 ; 85 for ( int i = 1 ; i <= mx ; i++) 86 { 87 ans +=sum[i]-1; 88// cout<<"sum[i]:"<<sum[i]<<endl; 89 } 90 cout<<ans<<endl; 91 92 93 94 #ifndef ONLINE_JUDGE 95 fclose(stdin); 96 #endif 97 return 0; 98}

http://acm.hdu.edu.cn/showproblem.php?pid=5630 题意：nm的棋盘，相邻格子的颜色相反，每次可以翻转一个任意大小矩形的格子，问最少需要翻转多少次使得棋盘的nm个格子颜色相同。（翻转的意思是颜色反色） 思路：手写了下。。发现。。答案就是n/2+m/2. 对应的最优策略是。。翻偶数行和偶数列，都翻一遍，颜色就一样了。

http://codeforces.com/contest/621/problem/A A. Wet Shark and Odd and Even time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Today, Wet Shark is given n integers. Using any of these integers no more than once, Wet Shark wants to get maximum possible even (divisible by 2) sum. Please, calculate this value for Wet Shark. Note, that if Wet Shark uses no integers from the n integers, the sum is an even integer 0.

http://codeforces.com/contest/621/problem/B B. Wet Shark and Bishops time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Today, Wet Shark is given n bishops on a 1000 by 1000 grid. Both rows and columns of the grid are numbered from 1 to 1000. Rows are numbered from top to bottom, while columns are numbered from left to right. Wet Shark thinks that two bishops attack each other if they share the same diagonal. Note, that this is the only criteria, so two bishops may attack each other (according to Wet Shark) even if there is another bishop located between them. Now Wet Shark wants to count the number of pairs of bishops that attack each other.

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=56 题意：给出一个长度为n的序列（无重复元素），询问经过多少次flip(i)操作，使得序列升序排列。定义flip(i)为将1到n-i+1的元素反转… 思路：先离散化，然后注意读入….