比赛中较...能做的5道题

 

hdoj6195. cable cable cable

题目链接 ： 　http://acm.hdu.edu.cn/showproblem.php?pid=6195

题目大意 ： 略

规律 ： 答案 = k+(m-k)*k

 

hdoj6198. number number number

题目链接　： http://acm.hdu.edu.cn/showproblem.php?pid=6198

题目大意  ： 给你一个整数n。问你n个斐波那契数（可重复）不能构成哪些数，输出最小的。

题解 ： 打表后很快能找到规律，答案就是第3+2*n项斐波那契数减一。然而O(N)的算法也会超时，需用矩阵优化，再矩阵快速幂。

 

hdoj6194. string string string

题目链接 ： http://acm.hdu.edu.cn/showproblem.php?pid=6194

题目大意 ： 给你一个串，求刚好出现k次的子串个数

题解 ： 后缀数组 + 线段树

　　后缀数组的SA数组存储了每个后缀（的下标），并且是按字典序排序好的。注意到这每个后缀的所有前缀，都加起来就是原串的所有子串，所以只看每个后缀的前缀之间的匹配就行了，刚好出现K次，那么就是这个前缀刚好连续地在SA数组中出现了k次，然而后缀数组还提供了一个height数组。

做法 ： 对height数组用线段树存储其[i,i+k-1]区间的最小值m，则这个区间中出现了k次的子串个数为m，再判断是否刚好出现k次，即与i-1，i+k比较，减去出现次数大于k的子串。k=1要特判。

AC代码：

#include
     
      #include
      
       #include
       
        #define M 100010using namespace std;struct node{    int l,r;    long long c;}; long long col[M*3],data[M];struct node arr[M*3];  int sa[M],rank1[M],height[M];int wa[M],wb[M],wv[M],ws[M];int num[M],s[M];int cmp(int *r,int a,int b,int l){    return r[a]==r[b]&&r[a+l]==r[b+l];}void get_sa(int *r,int n,int m)//求get函数{        int i,j,p,*x=wa,*y=wb,*t;    for(i=0;i
        
         =0;i--){if(ws[x[i]]-1<0) continue; sa[--ws[x[i]]]=i;}    for(j=1,p=1;p
         
          =j)y[p++]=sa[i]-j;        for(i=0;i
          
           =0;i--){if(ws[wv[i]]-1<0) continue;sa[--ws[wv[i]]]=y[i];} for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i
           
            mid) return Query(l,r,2*k+1); 　else 　　 return min(Query(l,mid,2*k),Query(mid+1,r,2*k+1)); }char s2[100010];int main(){ int T; scanf("%d",&T); while(T--) { int k,m=130,n; scanf("%d",&k); scanf("%s",s2); int i; for(i=0;s2[i];i++) num[i]=s2[i]; num[i]=0; n=i; get_sa(num,n+1,m); get_height(num,n); height[0]=0; height[n+1]=0; Construct(1,n,1); int sum=0,x,y; if(k==1){ for(int i=1;i<=n;i++) { if(n-sa[i]-max(height[i],height[i+1])>0) sum+=n-sa[i]-max(height[i],height[i+1]); } printf("%d\n",sum); continue; 　　　　 } k--; for(int i=2;i+k-1<=n;i++) { x=Query(i,i+k-1,1); if(height[i-1]>=x||height[i+k]>=x) continue; y=max(height[i-1],height[i+k]); sum+=x-y; } printf("%d\n",sum); } return 0;}
           
          
         
        
       
      
     

　hdoj6197. array array array

题目链接 ： http://acm.hdu.edu.cn/showproblem.php?pid=6197

题目大意 ： 给出数组A,整数K。判断是否能从数组A中抹去K个数后，使其非递增或非递减

题解 ： LIS。数组A长度减去最长非递增子序列长度若不大于K，则能构成非递增。非递减同理。

AC代码：

 

#include
     
      #include
      
       #include
       
        #define inf 1<<30#define MAXN 100005using namespace std;int ans[MAXN], a[MAXN],b[MAXN], dp[MAXN], n;  int len;int main(){        int T,len1,len2;    scanf("%d",&T);    while(T--)    {    int k;        scanf("%d%d",&n,&k);        for (int i = 1; i <= n; ++i)            scanf("%d",&a[i]);                ans[1] = a[1];        len = 1;                for (int i = 2; i <= n; ++i) {            if (a[i] >= ans[len]) {                ans[++len] = a[i];            } else {                int pos = upper_bound(ans, ans + len, a[i]) - ans;                ans[pos] = a[i];            }        }        len1=len;                for (int i = n; i >=1; --i)            b[n-i+1]=a[i];                                ans[1] = b[1];        len = 1;                for (int i = 2; i <= n; ++i) {            if (b[i] >= ans[len]) {                ans[++len] = b[i];            } else {                int pos = upper_bound(ans, ans + len, b[i]) - ans;                ans[pos] = b[i];            }        }        len2=len;        if(n-k<=len1||n-k<=len2) printf("A is a magic array.\n");        else printf("A is not a magic array.\n");        }    return 0;}
       
      
     

 

 

hdoj6201. transaction transaction transaction

题目链接 ： http://acm.hdu.edu.cn/showproblem.php?pid=6201

题目大意 ： 略

题解 ： 最短路。有趣的是点（城市）的权值只在开始和结束的时候起作用，那么自己设一个起点，其到每个点的边的权值即为每个点的权值，同理终点。这就转化成了求起点和终点的最短路问题，SPFA算法就好。别的算法不优化就会超时。

AC代码 ：

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define MAX_N 1000005#define MAX_M 1000005 using namespace std;struct edg{    int v,next,w;}e[MAX_M];bool inq[MAX_N];int d[MAX_N],p[MAX_N],eid=0;void add_edg(int u,int v,int w){    e[eid].v=v;    e[eid].w=w;    e[eid].next=p[u];    p[u]=eid++;    }  void spfa(int s) {    memset(inq, 0, sizeof(inq));    memset(d, 0x3f, sizeof(d));    d[s] = 0;    inq[s] = true;    queue
          
            q; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); inq[u] = false; for (int i = p[u]; i != -1; i = e[i].next) { int v = e[i].v; if (d[u] + e[i].w < d[v]) { d[v] = d[u] + e[i].w; if (!inq[v]) { q.push(v); inq[v] = true; } } } }}int main(){ int T; scanf("%d",&T); while(T--) { eid=0; memset(p,-1,sizeof(p)); int n,x,y,w; scanf("%d",&n); for(int i=0;i