a250. NCPC2011 Problem H Special Subsequences＠Morris' Blog

2011-10-16 21:15:13| 人氣1,453| 回應0 | 上一篇 | 下一篇

a250. NCPC2011 Problem H Special Subsequences

推薦 0 收藏 0 轉貼0 訂閱站台

a250. NCPC2011 Problem H Special Subsequences

Problem H

Special Subsequences

Input File: ph.in

Time Limit: 5 seconds

Given a sequence of n integers x₁,x_{2, …,} x_nand an integer k, 1≦k≦n,
we want to know if there exists a consecutive subsequence x_i,x_{i+1, …,} x_j for
some i and j, 1≦i≦j≦n, such that the sum

Is divisible by k or not.

For example, let n = 7 and k = 6. In the sequence of 7 integers.

2,5,1,-4,5,9,3

The sum of the following consecutive subsequences can be divisible by k = 6.

1. i = 2, j = 3: 5+1 = 6,

2. i = 1, j = 6: 2+5+1-4+5+9 = 18,

3. i = 6, j = 7: 9+3 = 12,

We are going to write a very efficient program to solve the problem with
large numver of integers in a short span of time. It is required to print only
one particular solution, not all solutions. The solution we want to print is the
first such subsequence. The first solution is the one with the smallest value
of i. In the above example, the answer we want is i = 1 and j = 6. If there
are more than one solution with the same value of i, we want the one with
smallest valu of j.

輸入說明：

An instance of the problem consists of
1.         the number of integers n,
2.         the sequence of integer xi , 1 ≦i≦n, and
3.         the divisor k.
These data are stored in +2 lines in the input file.
1.         The first line is the integer n.
2.         The following is   lines are the n integers xi , 1≦i≦n. Each line
contains at most 20 integers.
3.         The last line is the integer k.
In this problem, we assume that 1≦ n ≦100000, and -230 ≦ xi ≦ 230.
    Note that the test data file may contain more than one instances. The last
instance is followed by a line containing a single 0.
在此將題目修改 1 ≦ k ≦ 2147483647, 並且將所有數字排在同一行並不會切割 

輸出說明：

The outputs for each test case are the two integers i and j which are the indexes of
the consecutive subsequence whose sum is divisible by k. Print exactly one space
between i and j. If there are no solution print “no solutions.”

範例輸入：

7
2 5 1 -4 5 9 3
6
10
11 -3 1 13 -5 6 1 -8 -4 5
10
0

範例輸出：

1 6
5 9

提示：

	
	×　求序列最小的區間總和可以被 k 整除
  

出處：

NCPC2011 (管理：morris1028)

作法 : 雜湊表
我稍微修改了一下題目範圍。

把(x₁,x_{2, …,} xi)%k 都找出來，接著找餘數相同的兩個總和後%k，

7
00 01 02 03 04 05 06 07
    2  5  1 -4  5  9  3
 0  2  7  8  4  9 18 21 總和
 0  2  1  2  4  3  0  3 %6 後的值

你可以發現 00 = 06 也就是區間 [1,6] 同等道理 01 = 03 也就是區間 [2,3]

/**********************************************************************************/
/* Problem: a250 "NCPC2011 Problem H Special Subsequences" from NCPC2011         */
/* Language: C (1232 Bytes)                                                      */
/* Result: AC(1s, 6.2MB) judge by this@ZeroJudge                                 */
/* Author: morris1028 at 2011-10-16 15:30:55                                     */
/**********************************************************************************/

#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#define oo 100000
int A[100000], HASH[1000000], size;
struct Node {
   int v, st, ed;
   int next;
}Node[100001];
int Ai, Aj;
void Update(int i, int j) {
   if(i < Ai || (Ai == i && j < Aj))
       Ai = i, Aj = j;
}
void insHash(int v, int idx) {
   int m = v%1000000;
   int now = HASH[m], pre = 0;
   while(now) {
       if(Node[now].v > v)
           break;
       else if(Node[now].v == v) {
           Node[now].ed = Node[now].ed < idx ? Node[now].ed : idx;
           Update(Node[now].st, Node[now].ed);
           return;
       }
       else pre = now, now = Node[now].next;
   }
   size++;
   if(!pre)   HASH[m] = size;
   else       Node[pre].next = size;
   Node[size].v = v, Node[size].st = idx, Node[size].ed = oo;
   Node[size].next = now;
   return;
}
int main(){
   int n, k, i;
   while(scanf("%d", &n) == 1 && n) {
       for(i = 0; i < n; i++)
           scanf("%d", &A[i]);
       memset(HASH, 0, sizeof(HASH));
       scanf("%d", &k);
       Ai = oo, Aj = oo, size = 0;
       int sum = 0;
       insHash(0, -1);
       for(i = 0; i < n; i++) {
           A[i] %= k;
           sum += A[i];
           sum %= k;
           if(sum < 0) sum += k;
           insHash(sum, i);
       }
       if(Aj != oo)
           printf("%d %d\n", Ai+2, Aj+1);
       else
           puts("no solutions.");
   }
   return 0;
}

我要檢舉

#a250#NCPC2011#Problem H#Special Subsequences

台長： Morris

您可能對以下文章有興趣

a084. NOI2001 Day1.2.反正切函数的应用

[ZJ][模擬水] a349. 2. 指令解譯器

[ZJ][spfa、尤拉路徑、bitmask] a416. 6. 城市馬拉松

[ZJ] d372. 4. 合法執行路徑問題

人氣(1,453) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:a258. NCPC2011 Problem F Inverse Affine Transform
此分類上一篇:a242. 第三題：絕對值總和的最小值

回應(0)