上午切了P1920

這道題是最優騙分+貪心

原題：

---

?

有N (1 <= N <= 1,000,000)個 true 或者false的問題。
其中答案是true的問題的個數有K種可能：t_1, t_2, t_3,..., t_K (0 <= t_i<= N; 0 <= K <= 10,000). 但是我們無法知道具體哪個問題的答案是true或false。

現在Bessie要回答這N個問題，為了在運氣最差的情況下答對的題目最多，她必須采取最優策略。比如有6個問題， N=6， k = 2, t_1 = 0, t_2 = 3. 也就是說，這6個問題中，真命題的個數可能是0個，也可能是3個。那么Bessie為了在運氣最差的情況答對的問題最多，她可以回答每個問題都是的答案都是false. 可以看出，如果她運氣好的話，她能答對6題，但如果運氣差的話（即有3到是true的問題），那么她只能答對3題（因為她的回答是6個false）。
因此，Bessie在最差的情況下能答對3題。
　　我們來看看，如果其它策略，Bessie能否在運氣最差的情況下答對的題目超過3題。比如：Bessie的回答是3個true, 3個false. 那么最壞的情況是什么呢？由于Bessie并不知道具體的某問題的答案，可能她全部答錯。也就是3個真命題，她的回答是false,而3個假命題，她卻剛好回答是yes,這種情況Bessie答對0道題，顯然沒有上面的策略優。

? 你的任務是：在采取最優策略下，她在運氣最差時，最多能答對幾道題

?

---

這道題有三種情況

全選false，則采取true最多的可能

全選true，則采取true最少的可能

找出相鄰差最大的兩個可能，取其差的中間值

情況1情況2不需要證明

情況3證明：

t_i設t_x 和 t_y是相鄰的兩個t_i（t_x>t_y）,FJ可以保證（t_x-t_y）/2個正確答案，他只需選擇N-[(t_x+t_y)/2]個正確答案，其余全部選擇false

?

代碼：

//Earl_WR 2017.1.19 #include <iostream> #include <cstdio> #include <string> #include <cstring> #include <algorithm> using namespace std; int result=0; int maxx=-1; int n,k; int a[10010],t_f,t_t,t_e; int read() {int x=0,f=1;char ch=getchar();while (ch<'0' || ch>'9'){if (ch=='-')f=-1;ch=getchar();}while (ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } void in() {n=read();k=read();for (int i=1;i<=k;i++){a[i]=read();} } int main() {//freopen ("test.in","r",stdin);//freopen ("test.out","w",stdout);in();sort(a+1,a+1+k);t_f=n-a[k];if (t_f>result)result=t_f;t_t=a[1];if (t_t>result)result=t_t;for (int i=1;i<=k;i++){if (a[i+1]-a[i]>maxx){maxx=a[i+1]-a[i];}}t_e=maxx/2;if (t_e>result)result=t_e;cout<<result<<endl;return 0; }

下午切了p1828

原題：

---

?

Oj上有很多題是聯系的，對于某一類型的題目，必須要把基礎的題目做完，再總結一段時間，才能夠去切不水的題目。
在noip最后一周，老師布置了很多很多的題目來切。
為了更好的備考，為了更好的打好基礎，老師規定切題的規則如下：
對于老師布置的某項基礎作業X，神犇必須要在做完基礎作業X之后的 ?下Z分鐘， （如果難理解，看樣例）才能開始做另外一項作業Y，按照老師的說法：間隔的時間是為了讓你反思的。

但神犇具有同時完成多項作業的能力，并且神犇切任何的題目只需要一分鐘！！

現在神犇想知道，他需要多少時間來完成作業，數據保證神犇可以完成作業。

---

?

?

這道題是經典的拓補排序題

題解見課本

代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <ctime> #include <iomanip> #include <algorithm> #include <cstdlib> #include <string> using namespace std; #define M 100000 struct T {int v,t; }q[M]; int head=1,tail=0,id[M],ans=0,now[M]; int map[1000][1000],m,n; void init() {memset(map,0,sizeof(map));memset(id,0,sizeof(id));cin>>n>>m;for(int i=1;i<=m;i++){int x,y,v;cin>>x>>y>>v;map[x][y]=v;id[y]++;} } void work() {for(int i=0;i<n;i++)if(id[i]==0){q[++tail].v=i;q[tail].t=1;}for(head=1;head<=tail;head++){for(int i=0;i<n;i++)if(map[q[head].v][i]){id[i]--;now[i]=max(now[i],q[head].t+map[q[head].v][i]);if(id[i]==0){q[++tail].v=i;q[tail].t=now[i];}}} } int main() {//freopen("1828.in","r",stdin);//freopen("1828.out","w",stdout); init();work();for(int i=1;i<=tail;i++){//cout<<i<<' '<<q[i].v<<' '<<q[i].t<<endl;ans=max(ans,q[i].t);}cout<<ans<<endl;return 0; }

完事

?

轉載于:https://www.cnblogs.com/Earl-WR/p/6307416.html

總結

以上是生活随笔為你收集整理的2017.1.19切题总结的全部內容，希望文章能夠幫你解決所遇到的問題。

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