2017.10.16队内互测——胡策
出題人：Byike，RC，lxt ，Q
本套題死宅氣息濃厚…
Problem 1 ：埃羅芒阿老師
題目來源：http://codevs.cn/problem/2913/
題目描述
埃羅芒阿老師是著名的插畫家， 她的工作是為
電擊文庫出版的的書畫插畫。快要到截稿日了，埃羅芒阿老師還在水>_<埃羅芒阿突然發現自己還有一大堆插畫沒有完成，如果不能在截稿時間內完成是要扣工資的。
于是埃羅芒阿老師把每個任務所需的時間和現在(0 時刻)距離每個任務截稿的時間記錄了下來，想要計算出最多可以完成多少任務。
輸入描述
第一行是一個整數 N，接下來 N 行每行兩個整數 T1,T2 描述一個任務： 完成這個任務需要 T1 秒，如果在 T2 秒之內還沒有完成任務，這個任務就到截稿時間了。
輸出描述
輸出一個整數 S，表示最多可以完成 S 個任務.
樣例輸入
4
100 200
200 1300
1000 1250
2000 3200
樣例輸出
3
數據范圍及提示
對于 30%的數據， N≤100；
對于 60%的數據， N≤10000；
對于 80%的數據， N < 150,000; T1 < T2 <
INT_MAX；
對于 100%的數據， N < 150,000; T1 < T2 <
LLONG_MAX;
所有數據保證隨機生成。
思路
按照截稿日期從小到大排序，截稿日期相同則按耗費時間從小到大排序。記錄當前選取任務的總時間sum，每次對于一個任務，若由sum結束時間到截稿時間間允許完成這項任務則直接加入答案，若不能則取出已選擇任務中耗費時間最多的任務，如果其耗費時間大于當前任務則與之交換，即選擇當前的而放棄耗費時間最大的，這里用堆來維護。
貪心策略：盡量使得后面任務的剩余時間多，可證
代碼
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> using namespace std; int n; unsigned long long sum,ans; struct ren {unsigned long long s,t;bool operator < (ren a)const{return s<a.s;} }l[200010]; priority_queue<ren>q; bool cmp(ren a,ren b) {return a.t==b.t?a.s<b.s:a.t<b.t;//寫法 } int main() {scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%I64d%I64d",&l[i].s,&l[i].t);sort(l+1,l+n+1,cmp);for(int i=1;i<=n;i++){if(l[i].t-sum>=l[i].s){q.push((ren){l[i].s,l[i].t});sum+=l[i].s;ans++;}else{ren k=q.top();if(k.s>l[i].s)//不會使后面剩余空間變小 { //不可以寫為if(l[i].t-(sum-k.s)>l[i].s),有可能會使后面剩余空間變小q.pop();q.push((ren){l[i].s,l[i].t});sum-=k.s;sum+=l[i].s;}}}printf("%I64d",ans);return 0; }Problem 2 ：名偵探柯南
題目來源：http://codevs.cn/problem/1089/
題目描述
鈴木次吉郎又一次向基德發出挑戰，而這次的挑戰是在鈴木號快車上，這輛一年只運行一次的快車上，乘客幾乎是固定不變的，尤其是 7 號車廂，這節車廂里的乘客每年都提前預定，而這么做的理由也只是為了參加在這輛車上獨有的推理謎題，不幸的是，因為今年毛利小五郎的出現，在這節車廂中出現真的殺人事件，現在為了找出兇手，車廂中的人被聚集到一起，共有 N 個人，他們一共會說 P 句證詞，但N 個人中會有 M 個人說謊， 但兇手只有一個，因為柯南還在尋找其他證據，為此你要通過他們說的話去判斷兇手是誰。
輸入描述
輸入第一行為 3 個數， N,M,P，分別表示有 N 個人， M 個人說謊， P 句證詞以下 N 行，每行一個人名（全部大寫）之后 P 行，每行開始為一個人名，后緊跟一個冒號和一個空格，后面是一句證詞（符合表中所列的格式，可能有廢話）證詞每行不超過 250 個字符輸入中不會出現連續的兩個空格，且每行開頭和結尾也沒有空格。
單詞注明： guilty
角色注明：
鈴木次吉郎：鈴木財團顧問， 愛好環游世界，在得知有關基德的事
件后， 揚言要親手逮捕基德（用自家的寶石來作為誘餌）
基德（KID）：本名黑羽快斗，為調查父親死亡真相而成為怪盜尋找
珍稀的寶石， 以此找出幕后真相， 也以鈴木拿寶石挑戰作契機尋找
寶石(詳情請見怪盜基德 1412)
江戶川柯南：原名工藤新一（滾筒洗衣機）， 在服用酒廠藥物后變小
而以柯南為名掩蓋自己未死的真相
毛利小五郎：一直劃水的偵探
輸出描述
輸出只有一行， 有三種情況：
1 ， 若確定一個兇手，則輸出兇手名字
2 ， 找到符合條件的兇手， 但有多個，輸出
“Cannot Determine” （不含引號）
3 ， 沒有找到符合條件的兇手， 即根據已知條件不能
確定任何一個可能的兇手，輸出“Impossible” （不
含引號）。
樣例輸入
3 1 5
MIKE
CHARLES
KATE
MIKE: I am guilty.MIKE: Today is Sunday.
CHARLES: MIKE is guilty.
KATE: I am guilty.
KATE: How are you??
樣例輸出
MIKE
數據范圍及提示
1<=N<=20 , 0<=M<=N ,1<=P<=100
數據保證不隨機生成。
兇手保證在 N 個人中，但他/她不一定說過話。
思路
枚舉犯人枚舉今天是星期幾，若合法則更新答案，但實現實在是惡心…代碼能力題
代碼
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<map> using namespace std; int n,m,p,t,f,ans; int tf[1010]; string s,now; string num[1010]; struct inf {int id;//說話者的編號 string sy;//證詞 }fl[1010]; map<string,int>name;//將人名映射到編號 const string days[]= {"Today is Monday.","Today is Tuesday.","Today is Wednesday.","Today is Thursday.","Today is Friday.","Today is Saturday.","Today is Sunday.", }; bool check(int a,int b) {if(tf[a]==-1){if(!b)f++;else t++;if(f>m)//超過給定人數不合法 return 1;if((n-t)<m)//同理 return 1;}if(tf[a]==-1){tf[a]=b;//記錄 return 0;}else{if(tf[a]==b)return 0;else return 1;//與之前的情況沖突 } } void solve(int k,string day) {memset(tf,-1,sizeof(tf));//記錄每人說的是真話1還是假話0 t=f=0;//t為未說謊的人數,f為說謊的人數 for(int i=1;i<=p;i++){int pos;pos=fl[i].sy.find("I am guilty.");if(~pos)//pos!=EOF但不可以寫為pos!=0 {if(check(fl[i].id,fl[i].id==k))return;//當前狀態不合法便退出 }pos=fl[i].sy.find("I am not guilty.");if(~pos){if(check(fl[i].id,fl[i].id!=k))return;}pos=fl[i].sy.find(" is guilty.");if(~pos){now=fl[i].sy;now.erase(pos,11);int b=name[now];if(check(fl[i].id,b==k))return;}pos=fl[i].sy.find(" is not guilty.");if(~pos){now=fl[i].sy;now.erase(pos,15);int b=name[now];if(check(fl[i].id,b!=k))return;}pos=fl[i].sy.find("Today is ");if(~pos){if(check(fl[i].id,fl[i].sy==day))return;}}if(ans&&ans!=k){printf("Cannot Determine");exit(0);//終止程序 }ans=k; } int main() {scanf("%d%d%d",&n,&m,&p);for(int i=1;i<=n;i++){cin>>num[i];name[num[i]]=i;}for(int i=1;i<=p;i++){cin>>s;s.erase(s.length()-1,1);//刪除':'fl[i].id=name[s];getline(cin,fl[i].sy);fl[i].sy.erase(0,1);}for(int i=1;i<=n;i++)//枚舉犯人 for(int j=0;j<=6;j++)//枚舉今天是星期幾 solve(i,days[j]);if(!ans)printf("Impossible");elsecout<<num[ans];return 0; }Problem 3 ：
題目來源：https://www.luogu.org/problem/show?pid=2246#sub
題目描述
一天， 翻閱 Dark Flame Master 黑暗筆記的邪王真眼使發現了筆記中所記載的不可視境界線的秘密。在黑暗筆記的某一頁， 她看見了一篇文章。 這篇文章里記載著尋找不可視境界線并前往異世界的方法。
這篇文章由英文字母、和空白字符（制表/空格/回車）構成，但由于管理局的介入，字母的大小寫變得十分混亂，換行和空格也不成章法。
Dark Flame Master 告訴邪王真眼使，這篇文章中其實隱含著一個數字 x，只要朝向不可視境界線并說出 x 次“闇の炎に抱かれて消えろっ！ ”就可以打開異世界的通道， 這個 x 就是”HelloWorld” 在文章中作為子序列出現的次數。
于是邪王真眼使重新閱讀了筆記并解放了“じゃおう シンガン” 的力量！
由于解放后的“じゃおう シンガン” 力量十分強大， 所以大小寫對于她而言毫無區別；因此， “hEllOWorLD” 這樣的子序列是可以的。 所有的空格回車和制表符都可以被她直接忽略掉；也就是說，“HelloWorld” 是可以的； 當然， “hE Llow oR ld” 也是可以的。
現在，借助邪王真眼使的力量， Dark Flame Master 需要幫助她計算出在這篇文章中“HelloWorld” 作為子序列出現的次數。由于答案可能很大， 請輸出結果對 1000000007(10^9+7)的余數。
輸入描述 輸入包含若干行。這些行的內容共同構成一篇文章（由于管理局的介入， 十分可能出現語法不通順的情況） 。文章以 EOF（文件結尾）結束。
輸出描述 輸出僅包含一個整數，表示這篇文章中“HelloWorld” 出現的次數。
樣例輸入
1
HhEeLlLlOoWwOoRrLlDd
樣例輸出
1
1536
樣例輸入
2
Gou Li Guo Jia Sheng Si Yi
Qi Yin Huo Fu Bi Qu Zhi
River can feed people
Also can race boats
Hall Ellen Ok Words locked
樣例輸出
2
273
數據范圍及提示
記 n 為輸入的文章的長度（字符數）。
對于 20%的數據， n <= 20。
對于 50%的數據， n <= 500。
對于所有的數據， 15 <= n <= 500000。
數據不保證隨機生成。 (╯▽╰)
被漆黑烈焰吞噬殆盡吧！
思路
簡單處理一下輸入，方法 1：設置DP數組f[i][j]表示字符串匹配到i位置，HELLOWORLD（模板串）匹配到j位置的方案數。將無關字母忽略，對于只存在模板串中字母的情況，轉移為：
f[i][j]=f[i-1][j];
if(s[i]==t[j])
f[i][j]+=f[i-1][j-1];
代碼
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; const int mod = 1000000007; int len; int f[500010][15]; string s,t; int main() {s+="*";//或者為'*',使string儲存開始下標為1 while(cin>>t)//與scanf寫法不同 s+=t;//string的方便之處 t="*HELLOWORLD";len=s.length()-1;for(int i=1;i<=len;i++)if(s[i]>='a')//轉換為大寫字母 s[i]-=32;for(int i=0;i<=len;i++)f[i][0]=1;//初始化為1,使得在之后的更新中可以加上字母本身長度1數量for(int i=1;i<=len;i++)//二維,i-1狀態的所以情況都已確定 for(int j=1;j<=10;j++){f[i][j]=f[i-1][j];//字符串匹配到i的位置,HELLOWORLD匹配到其中j的位置的方案數首先等于前一位置匹配到j位置的方案數 if(s[i]==t[j])//若當前位置i可以與j位置匹配,確定位置并過濾無關字符 f[i][j]+=f[i-1][j-1],f[i][j]%=mod;//乘法原理,每一個原串位置在i之前,模板串位置在j之前的字母都會與當前字母形成一個新的方案,累加答案 //不可直接寫作%=1e9+7,類型為double無法與int取模 }printf("%d",f[len][10]);return 0; }方法 2：設置DP數組f[i]表示以i號位置字母（模板串）結尾的子序列的方案數，由于少了一維，我們無法通過前一維找到可用來轉移的前一狀態，于是對i倒序枚舉，使得以i位字母在原串位置之前的所有字母結尾的方案數都已求出后才更新i位，保證由前向后轉移
轉移時，對于f[i]，在之前的串中出現時更新的方案數作為這一次的基數，然后再加上以前一位字母（模板串）結尾的子序列方案數即：
f[i]=f[i]+f[i-1];
原理：f[i-1]包含了f[1~i-1]的答案
Problem 4 ：
題目來源：https://www.luogu.org/problem/show?pid=3927
題目描述
銀桑、神樂、新八三人在測試阿姆斯特朗回旋加速噴氣式阿姆斯特朗炮的威力。
阿姆斯特朗回旋加速噴氣式阿姆斯特朗炮十分神奇， 使用方式如下：
輸入兩個數字 n,k 到阿姆斯特朗回旋加速噴氣式阿姆斯特朗炮的控制臺中，然后阿姆斯特朗回旋加速噴氣式阿姆斯特朗炮會計算出 n!并把它轉化為 k 進制。最后 n!在 k 進制下末尾 0 的個數就是本次發射的威力，每個 0 代表 1 點威力。
為了測試時不造成太大的破壞，三人想知道每次測試，發射的威力有多大。
現在給出多組測試的 n 和 k， 請計算出每次發射的威力。
輸入描述
輸入文件為 amstl.in
題目包含多組數據， 以 EOF（文件結尾）為結束。所有題目數據保證不包含樣例。
long long 類型輸入輸出請用%I64d。
對于每組數據，輸入一行兩個正整數 n,k；
輸出描述
輸出文件為 amstl.out
每組數據一行，包含一個整數，表示本次發射的威力。
樣例輸入
10 40
樣例輸出
2
數據范圍及提示
對于 30%的數據， n <= 1000000， k = 10
對于另外 10%的數據， n <= 20, k <= 20
對于另外 20%的數據， n <= 50， k <= 52
對于另外 10%的數據， n<=10^12， k = 2
對于 100%的數據， n <= 10^12， k <= 10^12
思路
對于一個數轉k進制數，在前數%k==0時（%后前數/k）使得末尾0的個數加一。
于是考慮對n！和k進行質因數分解，對n！進行質因數分解即對1~n中的數進行質因數分解——原理同之前的高校模擬賽：賽小城學數學 http://blog.csdn.net/qq_36693533/article/details/78218929
則答案為k的某一質因子（在1-n中的出現次數/在k中的出現次數）的最小值，即為k被n！整除的次數
代碼
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; ll n,ns,k,cnt1,cnt2,ans; int main() {while(~scanf("%lld%lld",&n,&k)){ans=1e17+7;for(int i=2;i<=sqrt(k)+1;i++)//至多不大于根號n {ns=n;//注意n的值不可以隨著循環改變 cnt1=0;cnt2=0;while(k%i==0)cnt1++,k/=i;if(cnt1){ll base=i;while(ns)cnt2+=(ns/base),ns/=base;//ns/base:1~ns中包含有base這個質因子的數的個數 ans=min(ans,cnt2/cnt1);//將k中某一質因子的個數在n中的倍數取min }}if(k>1)//當前k為一質因子 {cnt2=0;while(n)cnt2+=(n/k),n/=k;ans=min(ans,cnt2);}if(ans==1e17+7)ans=0;printf("%lld\n",ans);}return 0; }總結
以上是生活随笔為你收集整理的2017.10.16队内互测——胡策的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： IoTDB Can not establ
- 下一篇： xcode-select --insta