1. 首頁 > 生活百科 > >

Programiranje 方法記錄

生活百科

[COCI2017-2018#3] Programiranje題面翻譯題目描述Little Leticija正在準備編程考試 。雖然她已經解決了很多任務，但還有一個任務尚未解決，所以她正在向你尋求幫助 。您將獲得單詞S和Q查詢 。在每個查詢中，給出正整數A，B，C和D.假設單詞X由單詞S中位置A和B之間的字母組成，而單詞S中位置C和D之間的字母組成單詞Y.如果可以以某種方式重新排列單詞Y中的字母并獲得單詞X，則必須回答 。
輸入輸出格式** 輸入格式：**第一行輸入包含單詞S（1≤| S |≤50000） 。| S | 表示單詞S中的字符數，由英文字母的小寫字母組成 。第二行輸入包含正整數Q（1≤Q≤50000） 。以下Q行中的每一行包含來自任務的四個整數A，B，C i D（1≤A≤B≤| S |且1≤C≤D≤| S |） 。** 輸出格式：**對于每個查詢，如果可能，輸出“DA”（克羅地亞語為yes），如果不可能，則輸出“NE”（克羅地亞語為否） 。
輸入輸出樣例**輸入樣例#1： **
kileanimal22 2 7 71 4 6 7**輸出樣例#1： **
DANE輸入樣例#2：
abababba23 5 1 31 2 7 8**輸出樣例#2： **
DADA輸入樣例#3：
vodevovode25 8 3 62 5 3 6**輸出樣例#3： **
【Programiranje 方法記錄】NEDA說明在總分為50％的測試用例中，它將保持：1≤| S | ≤1000且1≤Q≤1000 。澄清第三個測試用例：在第一個查詢中，X =“vovo”，Y =“devo” 。在第二個查詢中，X =“odev” ， Y =“devo” 。
題目描述Little Leticija is preparing for a programming exam. Even though she has solved a lot of tasks, there’s one still left unsolved, so she is asking you for help. You are given the word S and Q queries. In each query, you are given positive integers A, B, C and D. Let’s say that word X consists of letters between positions A and B in word S, and word Y from letters between positions C and D in word S. For each query, you must answer if it is possible to somehow rearrange the letters in word Y and obtain word X.
輸入格式The first line of input contains the word S (1 ≤ |S| ≤ 50 000). |S| denotes the number of characters in word S, which consists of lowercase letters of the English alphabet. The second line of input contains the positive integer Q (1 ≤ Q ≤ 50 000).
Each of the following Q lines contains four integers A, B, C i D (1 ≤ A ≤ B ≤ |S| and 1 ≤ C ≤ D ≤ |S| ) from the task.
輸出格式For each query, output “DA” (Croatian for yes) if it is possible, and “NE” (Croatian for no) if it is not.
樣例 #1樣例輸入 #1kileanimal22 2 7 71 4 6 7樣例輸出 #1DANE樣例 #2樣例輸入 #2abababba23 5 1 31 2 7 8樣例輸出 #2DADA樣例 #3樣例輸入 #3vodevovode25 8 3 62 5 3 6樣例輸出 #3NEDA提示In test cases worth 50% of total points, it will hold: 1 ≤ |S| ≤ 1000 and 1 ≤ Q ≤ 1000.
Clarification? ?of? ?the? ?third? ?test? ?case:
In the first query, X=”vovo”, and Y=”devo”. In the second query, X=”odev”, and Y=”devo”.
審題題意轉化：“單詞\(X\)能以某種方式重新排列得到單詞\(Y\)”，其實就是兩個單詞中的元素相同，即每種字母出現的次數分別相同 。又一看詢問，“區間查詢”，于是我們想到用統計每一個字母出現次數的前綴和 ， 再用前綴和離線地比較每種字母出現的次數 。
具體地，我們用二維數組\(pre[i][j]\)來記錄從第\(1\)位到第\(i\)位，字母\(j\)出現的次數 。（方便起見 ， 直接用字母的\(ascii\)碼值表示字母）
比如 ， \(pre[5][97]=2\)就是指從第\(1\)位到第\(5\)位，字母\(a\)出現了兩次 。
從而，對于每一個詢問，我們只需要比較每種字母出現次數是否相等即可 。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=50005;int pre[N][30];char s[N];int q,len;int main(){ scanf("%s",s+1); len=strlen(s+1); for(int i=1;i<=len;i++) {for(int j=1;j<=26;j++) pre[i][j]+=pre[i-1][j];//分別記錄每種字母出現次數的前綴和pre[i][s[i]-'a'+1]++;//當前位對應字母累加 } scanf("%d",&q); while(q--) {int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);if(b-a!=d-c)//如果兩個單詞的長度不相等 ， 就肯定NE{puts("NE");continue;}bool flag=1;for(int i=1;i<=26;i++){int tmp1=pre[b][i]-pre[a-1][i];//a~b第i個字母出現次數int tmp2=pre[d][i]-pre[c-1][i];//c~d第i個字母出現次數if(tmp1!=tmp2)//若某個字母出現次數不相等，則直接判NE{flag=0;break;}}if(flag) puts("DA");else puts("NE"); } return 0;}

    推薦閱讀