Posts

poj 2886 题目链接 题意：n 个人围成一圈，每个人身上有一个数，可正可负。从第 k 个人开始出圈，如果第 k 个人身上的数是 X，X>0，就左边第 x 个没有出圈的人出圈，否则右边第 -X 个人出圈。第 k 个人出圈得到的糖果数目为 f(k)，f(x) 表示 x 的因子个数。现在问谁能拿到最多的糖果，并且拿到了多少糖果。

1053: [HAOI2007]反素数ant # Time Limit: 10 Sec Memory Limit: 162 MB Submit: 2750 Solved: 1559 [Submit][Status][Discuss] Description # 对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足：g(x)>g(i) 0<i<x，则称x为反质数。例如，整数1，2，4，6等都是反质数。现在给定一个数N，你能求出不超过N的最大的反质数么？

题目链接 题意：求约数个数恰好为n个的最小的x 思路：这道题是作为反素数的例题出现在acdreamer的博客里的。 但是实际上，这道题应该和反素数没有关系。 如果题目问的是最小的约数个数大于等于n的x，那么答案一定是反素数…打表就行了。。。

题目链接 题意：求区间 [a,b] 中约数最多的那个数，如果有多个，输出最小的。 思路：看起来好像和反素数没什么关系……只是打个约数个数的表。 但是实际上，所有的答案恰好都是反素数。 我们回顾反素数的定义：设 f(x) 为 x 的约数个数，那么如果 f(n)>f(i)（0<i<n），n 就被称为反素数。

acdreamer的博客 wiki上的反素数是什么鬼orz…完全不是一个东西吧。。。。 反素数直观得理解。。。就是一个约数特别多的数。。。因为素数的约数最少。。。所以约数多的数就叫反素数（？随便口胡的…

题目链接 题意：n 只青蛙，第 i 只位于 x[i]，舌头长度为 t[i]。m 只蚊子，第 i 只蚊子所在位置为 p[i]，蚊子的大小为 b[i]。 蚊子按照出现顺序输入。 一只青蛙能吃到蚊子当且仅当蚊子和青蛙在同一个位置，或者蚊子在青蛙右边并且与青蛙的距离小于等于该青蛙舌头的长度。

题目链接 题意：一个无穷数列，从1开始，初始第i个位置上为i，给出n个swap，每次交换两个位置的数。问交换 n 次以后得到的数列中，逆序对的个数。 思路： 官方题解： At first find the position of each element which is used in swap (using map). Now let’s find the answer. It consists of the two parts. First part is the number of inversions formed by only whose elements which took part in the swaps. They can be counted by one of the standard ways: mergesort or Fenwick tree. The second part is the number of inversions formed by pairs of elements where one element has been swapped even once, and the other element stayed at his position. Let’s consider the following test:

题意：给出n个数，两两做差的绝对值，共有m=n*(n-1)/2个，问其中的中位数是多少。特别地，当m为偶数的时候，中位数为第m/2个。 思路：二分中位数。 一开始还觉得由于中位数在整数意义上不连续不能二分。。。。

题目链接 题意：给出n个x轴上的坐标点，选取其中c个，问c个之中任意两个点的最小距离最大是多少。 思路：二分距离check合法性。 大水题。。。因为想把三分艹掉。。。三分的题又多和二分挂在一起。。。顺便就写了。。。。

题目链接 题意：圆上，询问任意一段弧中，任意两点的距离+两点的权值和的最大值。 思路： 1.环先拆成串，复制 1..n 到后面，变成 1..2n。 化简公式： 2 * h[u] + 2 * h[v] + dist(u, v) = 2 * h[v] + d[1] + d[2] + … + d[v-1] + 2 * h[u] - (d[1] + d[2] + … + d[u-1]).

题目链接 题意：有 n 个数，每次可以删除掉数值相同并且所在位置成等差数列（只删 2 个数或者只删 1 个数应该也是可以的），删掉这些数以后可以将剩下的数重新以任意顺序排列，称为一次操作。现在给出 m 个询问，每个询问一个区间 [l,r]，问删光区间 [l,r] 中的数最少需要的操作次数。

题目链接 题意：题意说得一点也不清楚，大意是在询问区间 [l,r] 中满足某条件的数。该条件是，该数的任何一段由奇数组成的数串必须有偶数长度，任何一段由偶数组成的数串必须有奇数长度。

题目链接 题意：给出 n 个数，然后 m 个询问，每个询问一个区间 [l,r]，问该区间中不同的数有多少个。 思路：离线处理+线段树的做法不多说了： 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :Fri 16 Sep 2016 11:34:32 PM CST 4File Name :code/spoj/dquery.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=3E4+7; 32const int M=2E5+7; 33int n,Q; 34int a[N]; 35int tree[N<<2]; 36map<int,int>mp; 37struct node 38{ 39 int l,r; 40 int id; 41 bool operator < (node b)const 42 { 43 if (r==b.r) return l<b.l; 44 return r<b.r; 45 } 46}q[M]; 47void PushUp( int rt) 48{ 49 tree[rt] = tree[rt<<1] + tree[rt<<1|1]; 50} 51void update( int p,int sc,int l,int r ,int rt) 52{ 53 if (l==r) 54 { 55 tree[rt]+=sc; 56 return; 57 } 58 int m = (l+r)>>1; 59 if (p<=m) update(p,sc,lson); 60 else update(p,sc,rson); 61 PushUp(rt); 62} 63int query(int L,int R,int l,int r,int rt) 64{ 65 if (L<=l&&r<=R) return tree[rt]; 66 int m = (l+r)>>1; 67 int ret = 0 ; 68 if (L<=m) ret += query(L,R,lson); 69 if (R>=m+1) ret+=query(L,R,rson); 70 return ret; 71} 72int ans[M]; 73int main() 74{ 75 #ifndef ONLINE_JUDGE 76 freopen("code/in.txt","r",stdin); 77 #endif 78 cin>>n; 79 for ( int i = 1 ; i <= n ; i++) scanf("%d",&a[i]); 80 cin>>Q; 81 for ( int i = 1 ; i <= Q ; i++) scanf("%d %d",&q[i].l,&q[i].r),q[i].id = i ; 82 sort(q+1,q+Q+1); 83 int cur = 1; 84 for ( int i = 1 ; i <= Q ; i++) 85 { 86 for ( ; cur <= q[i].r ; cur++) 87 { 88 if (mp[a[cur]]) update(mp[a[cur]],-1,1,n,1); 89 mp[a[cur]] = cur; 90 update(mp[a[cur]],1,1,n,1); 91 } 92 ans[q[i].id] = query(q[i].l,q[i].r,1,n,1); 93 } 94 for ( int i = 1 ; i <= Q ; i++) printf("%d\n",ans[i]); 95 #ifndef ONLINE_JUDGE 96 fclose(stdin); 97 #endif 98 return 0; 99} 之后补一个主席树的做法

题目链接 题意：题意是由伪代码给出的，手算模拟了一下（noip 初赛即视感），题意大概是说，给出两个数组 a 和 b，a 数组长度为 n，b 数组长度为 len，然后从 a 中截取连续的 len 个元素，称为数组 s，如果存在一种方法使得 s 中元素和 b 中的元素一一对应且每组和都大于等于 h，则称这个 s 是合法的。现在问 a 中有多少个合法的 s。 具体来说，对于样例 5 2 10 5 3 1 8 5 5 7

1756: Vijos1083 小白逛公园 # Time Limit: 10 Sec Memory Limit: 64 MB Submit: 1078 Solved: 353 [Submit][Status][Discuss] Description # 小新经常陪小白去公园玩，也就是所谓的遛狗啦…在小新家附近有一条“公园路”，路的一边从南到北依次排着n个公园，小白早就看花了眼，自己也不清楚该去哪些公园玩了。 一开始，小白就根据公园的风景给每个公园打了分-.-。小新为了省事，每次遛狗的时候都会事先规定一个范围，小白只可以选择第a个和第b个公园之间（包括a、b两个公园）选择连续的一些公园玩。小白当然希望选出的公园的分数总和尽量高咯。同时，由于一些公园的景观会有所改变，所以，小白的打分也可能会有一些变化。 那么，就请你来帮小白选择公园吧。

题目链接 题意：给出n个数，m个修改，每次修改后询问整个区间的最大连续子段。 思路：考虑一段区间，分成左右两个子区间，这段区间的最大子段有三种情况：只在左区间中，只在右区间中，既在左区间中又在右区间中。前两种很好维护，对于后一种，我们新增加线段树的两个域，mxl,mxr，分别表示一个区间中包含左端点在的最大字段和（也就是最大前缀和），和一个区间中包含右端点在的最大子段和（也就是最大后缀和），然后对于最大子段既在左区间又在右区间的情况，只需要合并【左区间的最大后缀和 】和【右区间的最大前缀和】就好。

题目链接 题意： how many pairs of integers l and r are there, such that 1 ≤ l < r ≤ n and sequence b = _a_1_a_2… a__l__a__r__a__r + 1… a__n has no more than k inversions. 我花了两个小时才看懂题。。。。一直没懂b数列中a[l]和a[r]怎么就挨着了。。。 其实意思是。。。只保留a数列中1..l和r..n的。。。构成b数列。。。然后b数列的逆序对数小于等于k.问这样的l,r的对数。

题目链接 题意：给出两个排列，定义 ord(p) 为排列 p 的顺序（字典序从小到大），定义 perm(x) 为顺序为 x 的排列，现在要求 1 ≤ n ≤ 200 000 思路：首先去学了一下康托展开和逆展开，其实就是对于这种排列问题的一个比较省空间的 hash 函数？

题目链接 题意：给出一个长度为n的数列，每个位置是0或者1，给出q个操作，操作有两种类型，分别是将一段区间中反转，和询问当前某位置是0还是1 思路：lazy标记。lazy[i]记录以i节点为根节点的子树对应的区间中被翻转的次数，初始为0.然后查询的时候，根据被翻转次数的奇偶性确定答案。

题目链接 题意：求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}