例58 連續子序列計數
問題描述
給定一個正整數序列，對其和可被給定整數d整除的所有連續子序列進行計數，這些子序列可能重疊，例如，序列 2, 1, 2, 1, 1, 2, 1, 2包含6個連續的子序列，其總和可被4整除：6個子序列為：第一到第八個數、第二到第四個數、第二到第七個數、第三到第五個數、第四到第六個數和第五到第七個數，
輸入
輸入的第一行由一個整數c（1<=c<=200）組成，即測驗用例的數量，
每個測驗用例包括兩行，第1行由兩個整數d（1<=d<=1 000 000）和n（1<=n<=50 000）組成，分別是子序列和的除數d和序列長度，測驗用例的第2行包含序列的n個元素，它們是介于1和1000000之間的整數，
輸出
對于每個測驗用例，輸出連續子序列的和可被d整除的子序列個數，
輸入樣例
2
7 3
1 2 3
4 8
2 1 2 1 1 2 1 2
輸出樣例
0
6
（1）編程思路，
定義陣列long long num[1000005]={0}，其中陣列num[i]保存前綴和除以d的余數為i的個數，
輸入給定的n個整數時，一邊輸入，一邊求出前綴和sum，再計算sum除以d的余數，對應的num[sum%d]元素值加1，余數為0的子序列一定能整除d，而余數相同的任意兩個子序列相減，得到的子序列也一定能被d整除，
所以用回圈遍歷所有的余數個數（即num[0]~num[d-1]），將num[i] *(num[i]-1)/2的值累加起來（兩兩組合），再加上num[0]的值，就是所求的答案，
（2）源程式，
#include <stdio.h>
#include <string.h>
long long num[1000005];
int main()
{
int t;
scanf("%d",&t);
while (t--)
{
long long ans=0;
long long sum=0;
long long a;
memset(num,0,sizeof(num));
long long d,n;
scanf("%lld%lld",&d,&n);
int i;
for (i=1;i<=n;i++)
{
scanf("%lld",&a);
sum+=a;
sum%=d;
num[sum]++;
}
ans+=num[0];
for (i=0;i<d;i++)
{
if(!num[i]) continue;
ans+=num[i]*(num[i]-1)/2; // 兩兩組合
}
printf("%lld\n",ans);
}
return 0;
}
習題58
58-1 越獄
題目描述
監獄有 n 個房間，每個房間關押一個犯人，有 m 種宗教，每個犯人會信仰其中一種，如果相鄰房間的犯人的宗教相同，就可能發生越獄，求有多少種狀態可能發生越獄，
輸入格式
輸入只有一行兩個整數，分別代表宗教數 m（1≤m≤108） 和房間數 n（1≤n≤1012），
輸出格式
輸出一行一個整數代表答案，答案對 100,003取模，
輸入樣例
2 3
輸出樣例
6
（1）編程思路，
n 個房間m 種宗教，每個房間犯人的宗教信仰選擇都有m種，按乘法原理知總的排列數為mn，這么多情況進行排列看哪些情況可能越獄不是很方便，本題可以采用間接的方法，即可能發生越獄的方案數=總的排列數-不會越獄的方案數，
求不會越獄的方案數就比較簡單了，第1個房間有m種宗教信仰選擇，而后面的n-1個房間都有m-1種可能選擇（由于必須滿足同種宗教不相鄰，因此第2個房間可選除了第1個房間已選之外的m-1種宗教信仰，第3個房間可選除了第2個房間已選之外的m-1種宗教信仰，…），由乘法原理知：不會越獄的方案數=m?(m?1)n?1
因此，可能發生越獄的方案數為： mn?m?(m?1)n?1
由于m和n數值較大，采用快速冪完成冪運算，
（2）源程式，
#include <stdio.h>
#define MOD 100003
long long quickPower(long long x,long long n)
{
long long p=1;
while(n)
{
if (n%2==1) p=p*x%MOD;
x=x*x%MOD;
n=n/2;
}
return p;
}
int main()
{
long long n,m;
scanf("%lld%lld",&m,&n);
printf("%lld",(quickPower(m,n)-m*quickPower(m-1,n-1)%MOD+MOD)%MOD);
return 0;
}
58-2 數字計數
問題描述
給定兩個整數a和b，將a和b之間的數字（包括a和b）寫在一個串列中，您的任務是計算串列中每個數字出現的次數，例如，a=1024，b=1032，則串列為
1024 1025 1026 1027 1028 1029 1030 1031 1032
串列中有10個0、10個1、7個2、3個3、4~9各1個，
輸入
輸入最多由500行組成，每行包含兩個數字a和b，其中0<a，b<100000000，輸入由一行“0”終止，該行不被視為輸入的一部分，
輸出
對于每對輸入，輸出一行，其中包含由單個空格分隔的十個數字，第一個數字是數字0的出現次數，第二個數字是數字1的出現次數，以此類推，
輸入樣例
1 10
44 497
346 542
1199 1748
1496 1403
1004 503
1714 190
1317 854
1976 494
1001 1960
0 0
輸出樣例
1 2 1 1 1 1 1 1 1 1
85 185 185 185 190 96 96 96 95 93
40 40 40 93 136 82 40 40 40 40
115 666 215 215 214 205 205 154 105 106
16 113 19 20 114 20 20 19 19 16
107 105 100 101 101 197 200 200 200 200
413 1133 503 503 503 502 502 417 402 412
196 512 186 104 87 93 97 97 142 196
398 1375 398 398 405 499 499 495 488 471
294 1256 296 296 296 296 287 286 286 247
（1）編程思路，
撰寫函式long long calc(long long n, int d)求1~n這n個整數的序列中數字d的個數，
下面以calc(3124,2)的計算為例進行說明，
從低位向高位處理：當處理個位時，可把個位變成2，那么前面有多少個數，那么就有多少個2，前面有0~312共有313個數，sum+=313，sum=313；
之后處理十位，2前面若取0~30，則個位可取0~9，共有31*10個，若前面是31時，十位后面可以取0,1,2,3,4，共有5個數；因此，sum+= 31*10 +5，sum=628；
之后處理百位：1前面可以取0~2共有3個數，這時百位可以取2（總是比3124小），后面可以取任意的數（00~99），這樣可以取3*100個，百位前面若取3時，因為百位的1小于2，后面沒法取；因此，sum+=3*100，sum=928；
最后處理千位，當千位為2時，后面可以取任意的數（000~999），這樣，sum+=1000，sum=1928，
故 calc(3124,2)的回傳值為1928，
（2）源程式，
#include <stdio.h>
long long num[12]={1LL};
long long calc(long long n, int d)
{
long long sum=0,left,a;
int i;
for (i=1; i<12 ; i++)
{
left=n/num[i];
if (d==0) left--;
sum+=left*num[i-1];
a=(n%num[i]-n%num[i-1])/num[i-1];
if (a>d) sum+= num[i-1];
else if (a==d) sum+=n%num[i-1] +1;
if (n<num[i]) break;
}
return sum;
}
int main()
{
int i;
for (i=1;i<12;i++)
num[i]=num[i-1]*10;
long long n,m;
while (scanf("%lld%lld",&n,&m ) && (n||m))
{
if (m>n)
{
long long t; t=n; n=m; m=t;
}
for (i=0; i<=9; i++)
printf("%lld ",calc(n,i)-calc(m-1,i));
printf("\n");
}
return 0;
}
58-3 選3個點
問題描述
給定n個點，各點的坐標均為整數，任選3個點（x1,y1）、（x2,y2）和（x3,y3），設
A=|x1y2 - y1x2 + x2y3 - y2x3 + x3y1 - y3x1|/2
試求所選取的3個點使得A為整數（0也算）的組合有多少種？
輸入
第一行包含測驗用例的個數t，之后每一個測驗用例占1行，該行中第一數是不同點的個數n（0 <n= 10000），緊接著是n對整數，每對描述一個點（Xi，Yi），并且-100000 <=Xi，Yi＝100000，所有這些數字都用一個空格隔開，
輸出
使用包含“Scenario#i:”的行開始每個測驗用例的輸出，其中i是從1開始的用例編號，然后列印一行，其中包含使得A為整數的3個點的組合種數，
輸入樣例
6
3 0 0 2 0 1 -3
3 0 0 2 1 1 -3
3 0 0 2 2 3 3
4 0 0 2 0 0 2 2 2
4 0 0 1 0 0 1 1 1
9 0 0 0 1 0 2 1 0 1 1 1 2 2 0 2 1 2 2
輸出樣例
Scenario #1:
1
Scenario #2:
0
Scenario #3:
1
Scenario #4:
4
Scenario #5:
0
Scenario #6:
48
（1）編程思路，
A=|x1y2 - y1x2 + x2y3 - y2x3 + x3y1 - y3x1|/2
=| y1*(x3-x2) + y2*(x1-x3) + y3*(x2-x1)|/2
要使A為整數，只有當y1*(x3-x2) + y2*(x1-x3) + y3*(x2-x1)為偶數時才成立，
對于任一坐標（x,y），可以通過(x&1,y&1)將其轉換為4種型別之一，
1）(0,0)表示坐標（x,y）中x、y均為偶數；
2）(0,1)表示坐標（x,y）中x為偶數，y為奇數；
3）(1,0)表示坐標（x,y）中x為奇數，y為偶數；
4）(1,1)表示坐標（x,y）中x、y均為奇數，
這樣對于每個點的坐標，可以將它歸屬為4種型別之一，用陣列num[i][j]保存各型別點的個數，
顯然，若在這4種型別的同種型別中任意選3個，則A肯定為整數，例如，若三個點均屬于(1,1)型別，即x1、y1、x2、y2、x3、y3均為奇數，則(x3-x2)、(x1-x3)、(x2-x1)均為偶數，所以 y1*(x3-x2) + y2*(x1-x3) + y3*(x2-x1)也是偶數，
若在某種型別中任選2個點，再在另一型別中選一個點，則A也是整數，因為在公式計算中3個點坐標可以看成無差別，因此不妨設點(x1,y1)和(x2,y2)型別相同，點(x3,y3)與它們型別不同，若點(x1,y1)和(x2,y2)的型別為(0,0)或(1,0)，y1和y2均為偶數，x1和x2同奇偶，(x2-x1)為偶數，不管點(x3,y3)型別如何，y1*(x3-x2) + y2*(x1-x3) + y3*(x2-x1)一定是“偶數+偶數+偶數”，也是偶數；若點(x1,y1)和(x2,y2)的型別為(0,1)或(1,1)，y1和y2均為奇數，x1和x2同奇偶，(x2-x1)為偶數，若點(x3,y3)選擇時x3與x1、x2同奇偶，(x3-x2)和(x3-x1)均為偶數，y1*(x3-x2) + y2*(x1-x3) + y3*(x2-x1)一定是“偶數+偶數+偶數”，也是偶數；若點(x3,y3)選擇時x3與x1、x2不同奇偶，(x3-x2)和(x3-x1)均為奇數，y1*(x3-x2) + y2*(x1-x3) + y3*(x2-x1)一定是“奇數+奇數+偶數”，也是偶數，
若在4種型別中任選3種型別，每種型別中選1個點，則A不會是整數，例如點(x1,y1)、(x2,y2)和(x3,y3)的型別分別為(0,0)、(0,1)和(1,0)，則y1、y3是偶數，y2是奇數，x1是偶數，x3是奇數，(x3-x1)為奇數，y1*(x3-x2) + y2*(x1-x3) + y3*(x2-x1)一定是“偶數+奇數+偶數”，是奇數，A不會是整數，其他組合分析類似，
由此可得：如果選取的3個點存在2個以上的型別相同，那么A一定是整數，
（2）源程式，
#include <stdio.h>
#include <string.h>
int main()
{
int t;
scanf("%d",&t);
int iCase=1;
while(t--)
{
int n;
scanf( "%d",&n );
int num[2][2];
memset(num,0,sizeof(num));
int i,j;
for (i=0; i<n; i++)
{
int x,y;
scanf("%d%d",&x,&y);
num[x&1][y&1]++;
}
long long sum=0;
for (i=0; i<2; i++)
for (j=0;j<2;j++)
{
long long temp=num[i][j];
sum += temp*(temp-1)*(temp-2)/6 + temp*(temp-1)*(n-temp)/2;
}
printf("Scenario #%d:\n%lld\n",iCase++,sum);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/421613.html
標籤：其他
下一篇：《Java編程思想》讀書筆記一