• Problem 1 埃羅芒阿老師
  • 題目來源
  • 題目描述
  • 題解
  • 代碼
• Problem 2 名偵探柯南
  • 題目來源
  • 題目描述
  • 題解
  • 代碼
• Problem 3 中二病
  • 題目來源
  • 題目描述
  • 題解
  • 代碼
• Problem 4 銀魂
  • 題目來源
  • 題目描述
  • 題解
  • 代碼

內存 128M
時間 每點1s

Problem 1 埃羅芒阿老師

題目來源

http://codevs.cn/problem/2913/

題目描述

埃羅芒阿老師是著名的插畫家，她的工作是為電擊文庫出版的的書畫插畫。
快要到截稿日了，埃羅芒阿老師還在水>_<
埃羅芒阿突然發現自己還有一大堆插畫沒有完成，如果不能在截稿時間內完成是要扣工資的。
于是埃羅芒阿老師把每個任務所需的時間和現在距離每個任務截稿的時間記錄了下來，想要計算出最多可以完成多少任務。

輸入描述
第一行是一個整數N，
接下來N行每行兩個整數T1,T2描述一個任務：完成這個任務需要T1秒，如果在T2秒之內還沒有完成任務，這個任務就到截稿時間了。

輸出描述
輸出一個整數S，表示最多可以完成S個任務.

樣例輸入
4
100 200
200 1300
1000 1250
2000 3200

樣例輸出
3

數據范圍及提示
對于30%的數據，N≤100；
對于60%的數據，N≤10000；
對于100%的數據，N < 150,000; T1 < T2 < INT_MAX；
所有數據保證隨機生成。

題解

貪心+堆
正解：先按截稿日期由小到大排序，這樣能使截稿晚的能余出時間照顧早的。//顯然
①然后從第一個開始，若當前任務所需時間+之前的總時間小于等于當前截稿時間，則扔進堆里，ans++。//能夠完成，更新now
若大于，這時要從它前面所有任務中選一個修理時間最長的（記為y）和它比較，
②若當前任務所需時間 > y，則不扔進堆中。//若替換，當前任務仍然不能完成；
③若當前任務所需時間 < y，則把y替換成當前任務。//當前任務能夠完成，ans數不變，使得now減小，更加優；
這樣能保證時間利用率最高，完成更多任務。

由于不夠優的選擇會在第三種情況下pop掉，所以答案是最優的；

代碼

#include<iostream> #include<cstdio> #include<algorithm> #include<queue> using namespace std; const int N=150000+500; int n,ans,now; struct node{int ned,lst; }a[N]; priority_queue<node> Q; bool operator < (node a,node b){return a.ned<b.ned; } bool cmp(node a,node b){return a.lst<b.lst; } int main(){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d%d",&a[i].ned,&a[i].lst);sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++){if(now+a[i].ned<=a[i].lst){Q.push(a[i]);ans++; now+=a[i].ned;continue;}node u=Q.top();if(u.ned<=a[i].ned) continue;Q.pop();now-=u.ned;Q.push(a[i]);now+=a[i].ned;}printf("%d",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個人中，但他/她不一定說過話。

題解

假設我們都讀入了
枚舉哪個人是罪犯和今天是星期幾
掃一遍判斷

讀入實在是太惡心了

代碼

先粘一波std？？
主要是輸入惡心，運用了很多string的函數

//num記錄編號為i的人的名字，name記錄名字的編號 #include<iostream> #include<cstdio> #include<map> #include<cstring> #include<string> #include<algorithm> using namespace std; int n , m , p , t , fl , ans = 0; int tf[25]; string s , now , num[25]; map<string , int>name; struct st {int id;string ta; }f[105]; 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, bool b) {if(tf[a] == -1){if(!b) fl ++ ;//說謊的人 else t ++ ;//誠實的人 if(fl > m)//說謊的人大于m return 1;if(n - t < m)//誠實的人大于n-m return 1;}if(tf[a] == -1){tf[a] = b;return 0;//標記這個人的狀態 0說謊 1誠實 }else{if(tf[a] == b)//沒有矛盾 return 0;return 1;//出現矛盾 一個人既說謊又誠實 } } void run(int cr , string day) {memset(tf , -1 , sizeof(tf));t = fl = 0;for(int i = 1 ; i <= p ; i ++){int pos;pos = f[i].ta.find("I am guilty.");//s.find(str)在s中尋找str這個字符串，返回起始位置的迭代器 //如果不存在 返回-1 -1取反為0 if(~pos){if(check(f[i].id , f[i].id == cr)) return ;}pos = f[i].ta.find("I am not guilty.");if(~pos){if(check(f[i].id , f[i].id != cr))return ;}pos = f[i].ta.find(" is guilty.");if(~pos){now = f[i].ta;now.erase(pos , 11);int bm = name[now];if(check(f[i].id , bm == cr))return ;}pos = f[i].ta.find(" is not guilty.");if(~pos){now = f[i].ta;now.erase(pos , 15);int bm = name[now];if(check(f[i].id , bm != cr))return ;}pos = f[i].ta.find("Today is ");if(~pos){if(check(f[i].id , f[i].ta == day))return ;}}if(ans&& ans != cr){cout<<"Cannot Determine";exit(0);//exit()通常是用在子程序中用來終結程序用的，使用后程序自動結束，跳回操作系統。//exit(0) 表示程序正常退出,exit⑴/exit(-1）表示程序異常退出。 }ans = cr; } int main() {freopen("kid.in","r",stdin);freopen("kid.out","w",stdout);cin>>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);//s.erase（pos，len）刪除起始于 pos位置 長度為len的子串 f[i].id = name[s];getline(cin , f[i].ta);//讀取整行文本到f[i].ta f[i].ta.erase(0,1);}for(int i = 1 ; i <= n ; i ++)for(int j = 0 ; j <= 6 ; j ++)run(i,days[j]);if(ans == 0)cout<<"Impossible";else cout<<num[ans];return 0; }

Problem 3 中二病

題目來源

https://www.luogu.org/problem/show?pid=2246#sub

題目描述

一天，翻閱Dark Flame Master黑暗筆記的邪王真眼使發現了筆記中所記載的不可視境界線的秘密。
在黑暗筆記的某一頁，她看見了一篇文章。這篇文章里記載著尋找不可視境界線并前往異世界的方法。
這篇文章由英文字母、和空白字符（制表/空格/回車）構成，但由于管理局的介入，字母的大小寫變得十分混亂，換行和空格也不成章法。
Dark Flame Master告訴邪王真眼使，這篇文章中其實隱含著一個數字x，只要朝向不可視境界線并說出x次“闇の炎に抱かれて消えろっ！”就可以打開異世界的通道，這個x就是”Hello World”在文章中作為子序列出現的次數。
于是邪王真眼使重新閱讀了筆記并解放了“じゃおう シンガン”的力量！
由于解放后的“じゃおう シンガン”力量十分強大，所以大小寫對于她而言毫無區別；因此，“hEllOWorLD”這樣的子序列是可以的。所有的空格回車和制表符都可以被她直接忽略掉；也就是說，“HelloWorld”是可以的；當然，“hE Llow oR ld”也是可以的。
現在，借助邪王真眼使的力量，Dark Flame Master需要幫助她計算出在這篇文章中“Hello World”作為子序列出現的次數。
由于答案可能很大，請輸出結果對1000000007(10^9+7)的余數。

輸入描述
輸入包含若干行。這些行的內容共同構成一篇文章（由于管理局的介入，十分可能出現語法不通順的情況）。
文章以EOF（文件結尾）結束。

輸出描述
輸出僅包含一個整數，表示這篇文章中“Hello World”出現的次數。

樣例輸入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。
數據不保證隨機生成。(╯▽╰)
被漆黑烈焰吞噬殆盡吧！

題解

一個水的一筆的DP
bool數組d[i][j]=1，表示i位置的字符在helloworld中的順序可以是j
f[i][j]表示到i位，長度為j的子序列的方案總數

dp[i][j]=dp[i-1][j]+dp[i-1][j-1] for(int i=1;i<=tot;i++){ for(int j=10;j>=1;j--){ if(d[i][j]){ f[j]=(f[j]%mod+f[j-1]%mod)%mod; } } }

如果i位字符編號可以是j
f[i-1][j] 它之前的長度為j的方案數可以累加到它
f[i-1][j-1] 它之前長度為j-1的方案數，末尾元素換成了i，是全新的方案，所以也可以累加到它
滾動數組

代碼

std寫的真棒！！！！ #include <iostream> #include <cstdio> #include <cstdlib> using namespace std; const int mod=1000000007; int main() {freopen("helloworld.in","r",stdin);freopen("helloworld.out","w",stdout);long long dp[11]={1};char c,hello[20]="?helloworld";while((c=getchar())!=EOF){for(int i=10;i>=1;i--)if(c==hello[i]||c+32==hello[i])dp[i]=(dp[i-1]+dp[i])%mod;}cout<<dp[10];fclose(stdin);fclose(stdout);return 0; } #include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int N=500000+500,mod=1000000007; char a; int tot; long long f[50]; bool d[N][15]; void read(){while(scanf("%c",&a)!=EOF){if(a>='A'&&a<='Z') a=a+32;switch(a){case('h'):{tot++;d[tot][1]=1;break;}case('e'):{tot++;d[tot][2]=1;break;}case('l'):{tot++;d[tot][3]=1;d[tot][4]=1;d[tot][9]=1;break;}case('o'):{tot++;d[tot][5]=1;d[tot][7]=1;break;}case('w'):{tot++;d[tot][6]=1;break;}case('r'):{tot++;d[tot][8]=1;break;}case('d'):{tot++;d[tot][10]=1;break;}}}} int main(){read(); f[0]=1;for(int i=1;i<=tot;i++){for(int j=10;j>=1;j--){if(d[i][j]){f[j]=(f[j]%mod+f[j-1]%mod)%mod;}}}printf("%lld",f[10]);return 0; }

Problem 4 銀魂

題目來源

https://www.luogu.org/problem/show?pid=3927

題目描述

銀桑、神樂、新八三人在測試阿姆斯特朗回旋加速噴氣式阿姆斯特朗炮的威力。
阿姆斯特朗回旋加速噴氣式阿姆斯特朗炮十分神奇，使用方式如下：
輸入兩個數字n,k到阿姆斯特朗回旋加速噴氣式阿姆斯特朗炮的控制臺中，然后阿姆斯特朗回旋加速噴氣式阿姆斯特朗炮會計算出n!并把它轉化為k進制。
最后n!在k進制下末尾0的個數就是本次發射的威力，每個0代表1點威力。
為了測試時不造成太大的破壞，三人想知道每次測試，發射的威力有多大。
現在給出多組測試的n和k，請計算出每次發射的威力。

輸入描述
輸入文件為amstl.in
題目包含多組數據，以EOF（文件結尾）為結束。
對于每組數據，輸入一行兩個正整數n,k；

輸出描述
輸出文件為amstl.out
每組數據一行，包含一個整數，表示本次發射的威力。

樣例輸入
10 40

樣例輸出
2
數據范圍及提示
0

題解

求n!在k進制下的末尾0的個數

樸素求法 int j=n!; while(1){if(j%k==0) {cnt++,j/=k;continue;}break; } return cnt;

顯然是過不了的
考慮將n!和k進行質因數分解
在n!中k的質因數組合的個數即為末尾0的個數

分解k
可以枚舉 2~根k 統計某個質因子的指數cnt1
而且不用判素數
如4，在枚舉2時，已經去除了因子中所有的2，不可能分解出4

分解n!
首先只需要分解在k中有的質因數
類似于賽小城學數學的分解方法，logn的分解出n!的某個質因子的個數cnt2

http://blog.csdn.net/loi_lxt/article/details/78044788

**統計質因數的方法：** f(a)=n/a+n/(a^2)+n/(a^3)+.....+n/(a^k) a^k<=n,a^(k+1)>n 以從1-9中統計2為例（有2的只有2,4,6,8,）；2 4 6 8 2 √ √ √ √ 4 2^2 √ √ 2 2^3 √ 1 顯然，分層統計了2的次數；

答案在 cnt1/cnt2中取min
注意判斷最后k剩下的是一個大于根k的質數的情況

代碼

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const long long inf=1e16+8; long long ans; long long n,k,cnt1,cnt2;int main(){freopen("amstl.in","r",stdin);freopen("amstl.out","w",stdout);while(scanf("%lld%lld",&n,&k)!=EOF){cnt1=0,cnt2=0;ans=inf;long long tmp=sqrt(k)+1;for(int i=2;i<=tmp;i++){cnt1=0,cnt2=0;while(k%i==0){cnt1++;k/=i;}if(!cnt1) continue;long long base=i;while(base<=n){cnt2+=(n/base);base*=i;}ans=min(ans,cnt2/cnt1);}cnt1=0,cnt2=0;if(k>1){long long base=k;while(base<=n){cnt2+=(n/base);base*=k;}ans=min(ans,cnt2);}if(ans==inf) ans=0;printf("%lld\n",ans); }return 0; }

總結

以上是生活随笔為你收集整理的10.16 Loi队内胡策 贪心+毒瘤输入+DP+数论的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。