Posts

题目链接 题意：求n！在k进制表示下有多少位。 思路：答案为[ log(1)+log(2)+…+log(N) ]+1 其中log的底数都是K 由于有多组数据，预处理一个log的前缀和。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :Tue 13 Sep 2016 05:13:15 PM CST 4File Name :code/loj/1045.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <set>-digits-of-factorial-k进制数的位 13#include <map> 14#include <string> 15#include <cmath> 16#include <cstdlib> 17#include <ctime> 18#define fst first 19#define sec second 20#define lson l,m,rt<<1 21#define rson m+1,r,rt<<1|1 22#define ms(a,x) memset(a,x,sizeof(a)) 23typedef long long LL; 24#define pi pair < int ,int > 25#define MP make_pair 26using namespace std; 27const double eps = 1E-8; 28const int dx4[4]={1,0,0,-1}; 29const int dy4[4]={0,-1,1,0}; 30const int inf = 0x3f3f3f3f; 31const int N=1E6+7; 32int n; 33int base; 34double sum[N]; 35int main() 36{ 37 #ifndef ONLINE_JUDGE 38 freopen("code/in.txt","r",stdin); 39 #endif 40 sum[0] = 0 ; 41 for ( int i = 1 ; i < N ; i++) sum[i] = sum[i-1] + log(i); 42 int T; 43 cin>>T; 44 int cas = 0 ; 45 while (T--) 46 { 47 scanf("%d%d",&n,&base); 48 double ans = sum[n]/log(base)+1; 49 printf("Case %d: %d\n",++cas,int(ans)); 50 } 51 #ifndef ONLINE_JUDGE 52 fclose(stdin); 53 #endif 54 return 0; 55}

感觉就是为了记录排列。。。重复之类的。。。用到的一个hash函数。。。？ 维基百科 讲解

题目链接 题意：现在有N个骑士进行M轮PK…现在告诉这M轮是谁站在台上…其将l~r所存在的骑士都打败..而若一个骑士被打败..就出局了..也就是不存在了…请输出每个骑士是被哪个骑士打败的(最后的胜利者输出0)…保证有解..

题目链接 题意：给出两个数组，每个数组 n 个数，分别为 a 和 b，给出 m 个操作，操作有两种类型，第一种是给出 x,y,k，表示从 a 数组的 x 坐标开始复制 k 个数到 b 数组的 y 到 y+k-1。 第二种操作是给出 x，询问当前 b[x] 是多少。

题目链接 题意：给出n个数，m个查询，每组查询一个区间[l,r]，问[l,r]中会被吃掉多少个（区间[l,r]中的数只有当其是其他所有数的因数时才不会被吃掉，顺便问一句。。a divide b 是 a除b，也就是b除以a,b/a的意思嘛23333）

题目链接 题意：给出n个数，求满足 i<j<k且a[i]>a[j]>a[k]的三元组有多少个。 思路：对于这种要求三个数满足条件的题目，老司机的经验是考虑中间那个数，这道题也不例外。

题目链接 题意：定义_f_(l, r, x)为区间[l,r]中x出现的次数。现在要求calculate the number of pairs of indicies i, j (1 ≤ i < j ≤ n) such that_f_(1, i, a__i) > f(j, n, a__j). 思路：可以通过o(n)预处理出f(1,i,a[i])和f[j,n,a[j]]，其实预处理的过程就是离散化的过程呢。。。

题目链接 题意：给出n和m，初始给出1«n个数，先相邻的两个数进行或操作（a[1]^a[2],a[3]^a[4]…），得到的新数列再相邻的两个数进行异或操作。

题目链接 题意： 在二维坐标平面内进行 n (1 ≤ n ≤ 2·10^5) 次操作。一共有三种类型操作。 1.add x,y 将点 (x,y) 加进坐标系。 2.remove x,y 将点 (x,y) 移除。 3.find x,y 找到点 (x,y) 右上角的点 (xp>x,yp>y)。如果有多个输出 x 最小的。如果还有多个输出 y 最小的。

poj 2828 题目链接 题意：n个人，每个人有一个rp值（用来区分不同的人），还有一个pos[i]，表示当第i个人来排队的时候插入到第pos[i]个人的后面（也就是排在位置pos[i]+1)

题目链接 题意：找两个不相交点集使得对于每一条边至少有一个顶点在点集中 思路：判断能否构成二分图。染色即可。 需要注意的是。。。答案有特判。。和样例不一样我还以为是自己做错了2333.

题目链接：题目链接 题意：给出一个无向图，该图是通过仅包含‘a’ ‘b’ ‘c’三个字母，以规则“i,j之间有边，当且仅当s[i]和s[j]相同，或者s[i]和s[j]在字母表中相邻”（也就是只有’a’和’c’是没有边相连的）得到的，现在问能否还原这个字符串，如果能，输出任意一个解。

题目链接：hdu 5285 题目lianjie 题意：给定n个小朋友，以及小朋友之间的关系，要求将小朋友分成两组，**并且每组至少一个人，**现在问能否这样分组，如果有解，输出两组的人数，并保证第一组的人数尽可能地大。

hdu 5215 思路：询问一个无向图，是否存在奇数环，以及是否存在偶数环。（不同的环之间可以有相同的点，不能有相同的边） 思路：一开始的想法是，根据染色的奇偶性，如果染色到某个之前染色过的点，和当前要染的颜色相同，说明存在奇数环，不同，说明存在偶数环。

链接

键盘足够爽了以后。。。 鼠标明显降低效率。。。 学会逐步脱离鼠标吧orz. 首先是chrome插件vimium vimium教程 Vimium 常用的按键功能解释： # 1 * **j：向下细微滚动窗口 k：向上细微滚动窗口** 2 * J：(**Shift+j的意思，以下大写全部表示加Shift)** 下一个标签页 K：上一个标签页 3 * d：向下滚动半个屏幕 u：向上移动半个屏幕 4 * **g+g（连续按两下g）：回到顶部** 5 * **G：到达页面底部** 6 * H：后退 L： 前进 7 * f：将当前网页上的所有可见链接/输入框分配一个快捷键，输入后就可以打开或者跳转到对应的输入框。如果按的是F，那么将在新窗口中打开页面（见上图） 8 * g+i：将光标 定位到输入框，如果有多个可以按Tab键切换 9 * x：关闭当前页面 X：恢复刚刚关闭的页面 10 * o：相当于Chrome中的地址栏，可以匹配历史记录、收藏夹并在当前窗口打开，或者直接打开一个网址或者搜索一个关键字（Chrome在全屏的时候地址栏死都出不来，有了它就解决这个一直困扰我的问题了！～），如果按的是O，则可以在新窗口中打开，非常非常方便！ 11 * g+s：查看网页的源代码 12 * r：重新载入当前网页（顺便提一句，这点上新浪微博和它是一样的，光标没有定位在发送框时，即便没有安装这个插件你也可以用j/k来控制页面上下滚动，用r在刷新，用f或者p来定位到发送框。而Gmail的快捷键如j,k上下移动光标也是类似，有兴趣大家可以再自己去了解一下一些常用web应用的快捷键）

hdu 2444题目链接 题意：判断一个有向图是否是二分图，是的话求最大匹配数。 思路：交叉染色判二分图，是的话跑遍匈牙利即可。1A. 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年09月01日 星期四 14时24分36秒 4File Name :code/hdu/2444.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 <map> 14#include <string> 15#include <cmath> 16#include <cstdlib> 17#include <ctime> 18#define fst first 19#define sec second 20#define lson l,m,rt<<1 21#define rson m+1,r,rt<<1|1 22#define ms(a,x) memset(a,x,sizeof(a)) 23typedef long long LL; 24#define pi pair < int ,int > 25#define MP make_pair 26using namespace std; 27const double eps = 1E-8; 28const int dx4[4]={1,0,0,-1}; 29const int dy4[4]={0,-1,1,0}; 30const int inf = 0x3f3f3f3f; 31const int N=205; 32int n,m; 33vector<int>edge[N]; 34int col[N]; 35int link[N]; 36bool vis[N]; 37void init() 38{ 39 for ( int i = 0 ; i <= n ; i++) edge[i].clear(); 40 ms(col,-1); 41} 42bool dfs( int u,int x) 43{ 44 col[u] = x; 45 int siz = edge[u].size(); 46 for ( int i = 0 ; i < siz; i++) 47 { 48 int v = edge[u][i]; 49 if (col[v]==1-x) continue; 50 if (col[v]==x) return false; 51 if (!dfs(v,1-x)) return false; 52 } 53 return true; 54} 55bool solve() 56{ 57 for ( int i = 1 ; i <= n ; i++) if (col[i]==-1) if (!dfs(i,0)) return false; 58 return true; 59} 60bool Find( int u) 61{ 62 int siz = edge[u].size(); 63 for ( int i = 0 ; i < siz; i ++) 64 { 65 int v = edge[u][i]; 66 if (vis[v]) continue; 67 vis[v] = true; 68 if (link[v]==-1||Find(link[v])) 69 { 70 link[v] = u; 71 return true; 72 } 73 } 74 return false; 75} 76int hung( int n) 77{ 78 int ans = 0 ; 79 ms(link,-1); 80 for ( int i = 1 ; i <= n ; i++) 81 { 82 ms(vis,false); 83 if (Find(i)) ans++; 84 } 85 return ans; 86} 87int main() 88{ 89 #ifndef ONLINE_JUDGE 90 freopen("code/in.txt","r",stdin); 91 #endif 92 while (~scanf("%d %d",&n,&m)) 93 { 94 init(); 95 for ( int i = 1 ; i <= m ; i++) 96 { 97 int u,v; 98 scanf("%d%d",&u,&v); 99 edge[u].push_back(v); 100 } 101 if (!solve()) 102 { 103 puts("No"); 104 } 105 else 106 { 107 int ans = hung(n); 108 printf("%d\n",ans); 109 } 110 } 111 #ifndef ONLINE_JUDGE 112 fclose(stdin); 113 #endif 114 return 0; 115}

hdu 4751 题目链接 题意：n个人，给出每个人认识的人的信息。问能否将这些人分成两组，保证每组至少1个人，并且两两互相认识。 思路：首先是反向建图。由于要求同组内两个人互相认识，那么两个人u,v，只要u不认识v或者v不认识有一个满足，就连接双向边u,v，表示u,v不能分到同一组。

uva10004题目链接 题意：给出一个无向图，问是否可以组成二分图。 思路：交叉染色法。 首先任意取出一个顶点进行染色，和该节点相邻的点有三种情况： **　1.未染色 那么继续染色此节点(染色为另一种颜色)**

3680: 吊打XXX # Time Limit: 10 Sec Memory Limit: 128 MBSec Special Judge Submit: 2043 Solved: 732 [Submit][Status][Discuss] Description # gty又虐了一场比赛，被虐的蒟蒻们决定吊打gty。gty见大势不好机智的分出了n个分身，但还是被人多势众的蒟蒻抓住了。蒟蒻们将 n个gty吊在n根绳子上，每根绳子穿过天台的一个洞。这n根绳子有一个公共的绳结x。吊好gty后蒟蒻们发现由于每个gty重力不同，绳 结x在移动。蒟蒻wangxz脑洞大开的决定计算出x最后停留处的坐标，由于他太弱了决定向你求助。 不计摩擦，不计能量损失，由于gty足够矮所以不会掉到地上。