A. 字典序最大的子序列
给定字符串 s,s 只包含小写字母, 请求出字典序最大的子序列.
两种做法.
1, 从'z'开始搜索到'a', 从当前位置开始搜索此字母, 把搜索到的添加到构造出的子序列的末端, 然后从本次搜索到的字母的最后一个位置继续开始搜. 直到搜完位置.
2, 将整个字符串倒序, 从头开始构造一个上升速度最快的不下降子序列即可.
- #include"stdio.h"
- #include"string.h"
- char s[105000];
- char a[105000];
- int main(){
- int i,l,x,now;
- scanf("%s",s);
- l=strlen(s);
- now=97;
- x=0;
- for (i=l-1;i>=0;i--){
- if (s[i]>=now) {
- a[x]=s[i];
- x++;
- now=s[i];
- }
- }
- for (i=x-1;i>=0;i--) printf("%c",a[i]);
- printf("\n");
- }
B. 漂亮的树
街上有 n 棵树, 标号为 1...n, 第 i 棵树的高度为 ai. 定义这 n 棵树是漂亮的, 当且仅当
1. 对于所有的 i,ai=a(n-i+1);
2. 对于 1 <= i <n / 2 (不是整除),ai + 1= ai + 1.
由于本题树高的限制, 极限情况不超过 10 万. 为了使树高为正, 我们在所有的树上都加 10 万, 即所有的树高不超过 20 万, 且大于 0. 在这之后, 我们可以发现, 对于每一颗树, 它们都唯一属于一个分类, 即当第 1 颗树为 k 时, 这颗树是漂亮的. 所以将每一颗数分类, 然后找到最大的类即可. 答案为 n - 最大的类的 size.
- #include"stdio.h"
- #include"string.h"
- #include"vector"
- using namespace std;
- int v[505000];
- int a[505000];
- int main(){
- int n,i;
- scanf("%d",&n);
- for (i=1;i<=n;i++) {scanf("%d",&a[i]);a[i]+=100000;}
- memset(v,0,sizeof(v));
- for (i=1;i<=(n+1)/2;i++) {
- if (a[i]-i+1>0) v[a[i]-i+1]++;
- }
- for (i=(n+1)/2+1;i<=n;i++) {
- if (a[i]-(n-i)>0) v[a[i]-(n-i)]++;
- }
- int ans=0;
- for (i=1;i<=500000;i++) if (v[i]>ans) ans=v[i];
- printf("%d\n",n-ans);
- }
C. 任意点
平面上有若干个点, 从每个点出发, 你可以往东南西北任意方向走, 直到碰到另一个点, 然后才可以改变方向. 请问至少需要加多少个点, 使得点对之间互相可以到达.
很厉害的题啊, 完全没有想到是并查集.
我们将所给的点分类, 分成一块一块的. 块内的任意两个点均可达. 可以发现, 若两个点的横坐标或者纵坐标相同, 那么它们一定是一个块的. 然后, 找到块的个数. 此时, 我们添加一个点, 就可使两个块联通. 当然, 添加一个点, 也最多可使两个点联通. ans = 块的个数 - 1.
- #include"stdio.h"
- #include"string.h"
- int x[105];
- int y[105];
- int vis[105];
- int father[105];
- int getfather(int k){
- if (k==father[k]) return k;
- else father[k]= getfather(father[k]);
- return father[k];
- }
- int main(){
- int n,i,j,a,b,ans;
- ans=0;
- scanf("%d",&n);
- for (i=1;i<=n;i++) father[i]=i;
- for (i=1;i<=n;i++) scanf("%d %d",&x[i],&y[i]);
- for (i=1;i<=n;i++)
- for (j=i+1;j<=n;j++)
- if (x[i]==x[j]||y[i]==y[j]) {
- a=getfather(i);
- b=getfather(j);
- father[b]=a;
- }
- for (i=1;i<=n;i++) father[i]=getfather(father[i]);
- memset(vis,0,sizeof(vis));
- for (i=1;i<=n;i++) if (vis[father[i]]==0){
- vis[father[i]]=1;
- ans++;
- }
- printf("%d\n",ans-1);
- }
E. 求值
给定 n 个数字 a1, a2, ..., an. 定义 f(l, r) = al | al+1| ... | ar. 现在枚举(1 <= l <= r <= n), 问不同的 f 值一共有多少个.
呃.. 讲讲我 tle 的做法.
首先线段树处理完从 [l,r] 的或和. 处理完每个位置的倍增. 然后从 1 到 n 枚举每一个位置. 从当前位置开始尝试倍增最大的量, 如果倍增完之后到达的位置的或和不变, 则直接跳过去. 否则, 二分跳的长度, 也就是先跳一半的距离, 继续尝试到达那个点的或和是不是不变. 若不变, 则跳, 否则继续迭代. 直到, 往前跳一个位置. 复杂度约为 O(n(logn)^2). 然后光荣的 T 了.
正确的做法如下.
由于数不超过 2^20. 也就是说, 在每一个位置往后跳的次数, 最多不过 20 次. 所以我们只需要预处理在当前位置的或的每一位, 在哪些点最先会被改变. 处理出这个之后, 按点的先后排序, 然后从最先出现的点开始或, 或好了一个位置, 加入到 set 中. 最后输出 set 的 size.
那么现在问题在于, 如何快速预处理出, 在当前位置的或的每一位, 在哪些点最先会被改变. 从后往前递推即可. 若为 1, 跟新, 反之, 从后面获得.
- #include"stdio.h"
- #include"string.h"
- #include"set"
- #include"algorithm"
- #define maxn 105000
- using namespace std;
- set<int>s;
- int a[maxn][21];
- int b[maxn];
- int sign[50];
- struct node{
- int wei,sum;
- }xu[50];
- int cmp1(node a,node b){
- return a.sum<b.sum;
- }
- int main(){
- int i,n,x,now,l,j;
- int ff=0;
- scanf("%d",&n);
- for (i=1;i<=n;i++) scanf("%d",&b[i]);
- memset(a,-1,sizeof(a));
- for (i=n;i>=1;i--){
- l=0;
- x=b[i];
- if (b[i]==0) ff=1;
- memset(sign,0,sizeof(sign));
- while(x>0){
- l++;
- sign[l]=x%2;
- x=x/2;
- }
- for (j=1;j<=20;j++)
- if (sign[j]==1) a[i][j]=i;
- else a[i][j]=a[i+1][j];
- }
- s.clear();/*
- for (i=1;i<=n;i++){
- for (j=1;j<=20;j++) printf("]",a[i][j]);
- printf("\n");
- }*/
- for(i=1;i<=n;i++) {
- now=b[i];
- for (j=1;j<=20;j++) {
- xu[j].wei=j;
- xu[j].sum=a[i][j];
- }
- sort(xu+1,xu+1+20,cmp1);
- xu[21].sum=-1;
- for (j=1;j<=20;j++) if (xu[j].sum!=-1) {
- if (xu[j].sum!=xu[j+1].sum){
- now=now|(1<<(xu[j].wei-1));
- s.insert(now);
- }else {
- now=now|(1<<(xu[j].wei-1));
- }
- }
- }
- printf("%d\n",s.size()+ff);
- }
F. 选值
给定 n 个数, 从中选出三个数, 使得最大的那个减最小的那个的值小于等于 d, 问有多少种选法.
尺取法即可.
- #include"stdio.h"
- long long a[105000];
- int main(){
- long long n,m,i;
- scanf("%lld %lld",&n,&m);
- for (i=1;i<=n;i++) scanf("%lld",&a[i]);
- long long r=1;
- long long ans=0;
- for (i=1;i<=n;i++){
- while(r<=n&&a[r]-a[i]<=m) r++;
- if (r-1-i>=2) ans+=(r-1-i)*(r-1-i-1)/2;
- }
- printf("%lld\n",ans);
- }
来源: http://www.bubuko.com/infodetail-2588327.html