小Q系列故事——屌絲的逆襲
Time Limit : 300/100ms (Java/Other)Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 1Accepted Submission(s) : 1
Problem Description 畢業於普通本科的小Q一直自稱是資深屌絲，不僅學校不知名，甚至他自己在這個普通學校也是默默無聞——直到臨近畢業的時候，班裡5朵金花中的2位甚至從沒和他說過話！
誰又能想到，如此不起眼的小Q在歷經重重面試環節後，竟然如願以償加入了心儀已久的騰訊公司！消息剛剛傳開的那幾天，這在他們班甚至整個學院都是討論的熱門話題，如果這時候你還表示不知道小Q是誰，你都會被大家當作怪物的。
正所謂野百合也有春天，屌絲也有逆襲的那一天！
剛到騰訊大廈上班的那幾天，小Q眼中的一切都是那麼新鮮，連每天見到的前台MM在他眼中都胖的那麼可愛。小Q就這樣在緊張與興奮的情緒中度過了一天又一天，每天即勤奮認真又小心翼翼，很希望能給主管留下個好印象，以免失去這來之不易的工作機會。
一段時間以後，隨著對工作環境以及同事的熟悉，小Q逐漸放松下來，在工作間隙，他細細觀察了自己的工作環境，發現整個工作室是一個N行M列的矩形布局，或者是因為屌絲的本性逐步暴露，他還暗自給每個同事在心裡進行了魅力值評分（為區別男女，男生一律用負整數表示，女生一律用正整數表示）。
現在，小Q把所有人的數據記錄下來，並且這樣定義一個位置的價值：
1、一個位置的價值只和其上下左右四個鄰居的魅力值有關（對於靠邊的位置，只考慮其存在的鄰居）；
2、如果某位置的鄰居和該位置主人性別不同，則總分加上鄰居魅力值的絕對值，否則減去；
3、對周圍所有鄰居的數據處理後，最終的得分即為這個位置的最終得分，得分越高，則該位置越好；
現在你能幫助小Q計算一下哪裡才是最佳位置嗎？
Input 輸入包含多組測試數據； 每組測試數據的第一行包含2個整數N和M，表示工作室的布局是N行M列； 接下來的N行，每行有M個整數，分別表示對應位置員工的魅力值數據Ki，正整數表示女生的魅力值，負整數表示男生的魅力值； N和M為0的時候表示輸入數據結束。 [Technical Specification] N<=20 M<=20 -100<=Ki<=100
Output 請計算並輸出最佳位置的行列號以及對應的得分，如果得分最高的位置有多個，則請輸出行號最小的那個，行號還相同的話，再比較列號，只輸出列號最小的那個即可。
Sample Input
2 3 5 -4 3 -6 3 7 0 0
Sample Output
1 2 11
#include
#include
using namespace std;
int ary[25][25];
int n,m;
int sum;
void fun(int x,int y,int num)
{
if(x < 1 || x > n || y < 1 || y > m)
return ;
if(ary[x][y] * num < 0)
{
sum += abs(ary[x][y]);
}
else
sum -= abs(ary[x][y]);
}
int main()
{
int i,j,k;
int t;
int a,b;
int cnt;
while(~scanf("%d%d",&n,&m),n&&m)
{
memset(ary,0,sizeof(ary));
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
scanf("%d",&ary[i][j]);
}
int maxn = 0;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
sum = 0;
fun(i-1,j,ary[i][j]);
fun(i+1,j,ary[i][j]);
fun(i,j-1,ary[i][j]);
fun(i,j+1,ary[i][j]);
if(sum > maxn)
{
a = i;
b = j;
maxn = sum;
}
}
}
printf("%d %d %d\n",a,b,maxn);
}
return 0;
}
小明系列故事——買年貨
Time Limit : 5000/2000ms (Java/Other)Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 1Accepted Submission(s) : 1
Problem Description 春節將至，小明要去超市購置年貨，於是小明去了自己經常去的都尚超市。
剛到超市，小明就發現超市門口聚集一堆人。用白雲女士的話說就是：“那家伙，那場面，真是人山人海，鑼鼓喧天，鞭炮齊呤，紅旗招展。那可真是相當的壯觀啊！”。好奇的小明走過去，奮力擠過人群，發現超市門口貼了一張通知，內容如下：
值此新春佳節來臨之際，為了回饋廣大顧客的支持和厚愛，特舉行春節大酬賓、優惠大放送活動。凡是都尚會員都可用會員積分兌換商品，凡是都尚會員都可免費拿k件商品，凡是購物顧客均有好禮相送。滿100元送bla bla bla bla，滿200元送bla bla bla bla bla...blablabla....
還沒看完通知，小明就高興的要死，因為他就是都尚的會員啊。迫不及待的小明在超市逛了一圈發現超市裡有n件他想要的商品。小明順便對這n件商品打了分，表示商品的實際價值。小明發現身上帶了v1的人民幣，會員卡裡面有v2的積分。他想知道他最多能買多大價值的商品。
由於小明想要的商品實在太多了，他算了半天頭都疼了也沒算出來，所以請你這位聰明的程序員來幫幫他吧。
Input 輸入包含多組測試用例。 每組數據的第一行是四個整數n，v1，v2，k； 然後是n行，每行三個整數a，b，val，分別表示每個商品的價錢，兌換所需積分，實際價值。 [Technical Specification] 1 <= n <= 100 0 <= v1, v2 <= 100 0 <= k <= 5 0 <= a, b, val <= 100 Ps. 只要錢或者積分滿足購買一件商品的要求，那麼就可以買下這件商品。
Output 對於每組數據，輸出能買的最大價值。 詳細信息見Sample。
Sample Input
5 1 6 1 4 3 3 0 3 2 2 3 3 3 3 2 1 0 2 4 2 5 0 0 1 0 4 4 1 3 3 4 3 4 4
Sample Output
12 4
三重背包
#include
#include
using namespace std;
int dp[105][105][105];
struct node
{
int a,b,w;
}list[105];
inline int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int i,j,k,kk;
int t;
int a,b;
int cnt;
int n,m,v1,v2;
while(~scanf("%d%d%d%d",&n,&v1,&v2,&kk))
{
for(i=1;i<=n;i++)
scanf("%d%d%d",&list[i].a,&list[i].b,&list[i].w);
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
{
for(t=kk;t>=0;t--)
{
for(j=v1;j>=0;j--)
{
for(k=v2;k>=0;k--)
{
int temp = 0;
if(t>=1)
temp = max(temp,dp[t-1][j][k] + list[i].w);
if(j-list[i].a>=0)
temp = max(temp,dp[t][j-list[i].a][k] + list[i].w);
if(k-list[i].b>=0)
temp = max(temp,dp[t][j][k-list[i].b] + list[i].w);
dp[t][j][k] = max(dp[t][j][k],temp);
}
}
}
}
printf("%d\n",dp[kk][v1][v2]);
}
return 0;
}
吉哥系列故事——臨時工計劃
Time Limit : 3000/1000ms (Java/Other)Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 3Accepted Submission(s) : 1
Problem Description 俗話說一分錢難倒英雄漢，高中幾年下來，吉哥已經深深明白了這個道理，因此，新年開始存儲一年的個人資金已經成了習慣，不過自從大學之後他不好意思再向大人要壓歲錢了，只能把唯一的希望放到自己身上。可是由於時間段的特殊性和自己能力的因素，只能找到些零零碎碎的工作，吉哥想知道怎麼安排自己的假期才能獲得最多的工資。
已知吉哥一共有m天的假期，每天的編號從1到m，一共有n份可以做的工作，每份工作都知道起始時間s，終止時間e和對應的工資c，每份工作的起始和終止時間以天為單位(即天數編號)，每份工作必須從起始時間做到終止時間才能得到總工資c，且不能存在時間重疊的工作。比如，第1天起始第2天結束的工作不能和第2天起始，第4天結束的工作一起被選定，因為第2天吉哥只能在一個地方工作。
現在，吉哥想知道怎麼安排才能在假期的m天內獲得最大的工資數（第m+1天吉哥必須返回學校，m天以後起始或終止的工作是不能完成的）。
Input 第一行是數據的組數T；每組數據的第一行是2個正整數：假期時間m和可做的工作數n；接下來n行分別有3個正整數描述對應的n個工作的起始時間s，終止時間e，總工資c。 [Technical Specification] 1<=T<=1000 9
Output 對於每組數據，輸出吉哥可獲得的最高工資數。
Sample Input
1 10 5 1 5 100 3 10 10 5 10 100 1 4 2 6 12 266
Sample Output
102
01背包
#include
#include
#include
using namespace std;
int dp[105];
struct node
{
int a,b,w;
}list[1105];
inline int max(int a,int b)
{
return a>b?a:b;
}
int cmp(node aa,node bb)
{
if(aa.a == bb.a)
return aa.b < bb.b;
return aa.a < bb.a;
}
int main()
{
int i,j,k,kk;
int N;
int t;
int a,b,w;
int cnt;
int n,m,v1,v2;
scanf("%d",&N);
while(N-- && scanf("%d%d",&m,&n))
{
for(i=1,k=1;i<=n;i++)
{
scanf("%d%d%d",&list[i].a,&list[i].b,&list[i].w);
if(list[i].a > m || list[i].a < 1)
{ i--;n--;}
}
sort(list+1,list+1+n,cmp);
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
{
for(j=m;j>=list[i].b;j--)
{
dp[j] = max(dp[j],dp[list[i].a-1]+list[i].w);
}
}
printf("%d\n",dp[m]);
}
return 0;
}
湫湫系列故事——植樹節
Time Limit : 1000/500ms (Java/Other)Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 1Accepted Submission(s) : 1
Problem Description 今天是一年一度的植樹節，騰訊幼兒園要求每個老師在班裡選出幾個小朋友一起去野外種植小樹苗，根據學校的整體安排，湫湫老師的班裡要選出3個小朋友。已知湫湫的班裡共有n個孩子，每個孩子有Bi個朋友(i從1到n)，且朋友關系是相互的，如果a小朋友和b小朋友是朋友，那麼b小朋友和a小朋友也一定是好朋友。為了選擇的公平性，湫湫老師會隨機抽取3個小朋友出來(每個人被抽到的概率相同)，但是她很希望這3個小朋友之間的關系完全相同，湫湫老師想請你幫她算算抽到的3個小朋友正好關系相同的概率是多少？
PS. 關系相同就是指要麼3個人互相是好朋友，要麼3個人互相都不是好朋友。
Input 輸入數據第一行是一個整數T(1<=T<=1000)，表示輸入數據的組數；每組數據的第一行是一正整數n表示孩子的總數(2
Output 對於每組數據，請輸出抽到的3個小朋友關系相同的概率，結果保留3位小數。
Sample Input
1 5 3 3 3 3 4
Sample Output
0.400
概率題數學題
#include
#include
#include
using namespace std;
int main()
{
int i,j,k,kk;
int N;
int t;
int a,b,w;
int cnt,n;
int ary[1005];
int sum;
scanf("%d",&N);
while(N-- && scanf("%d",&n))
{
for(i=1,sum=0;i<=n;i++)
{
scanf("%d",&ary[i]);
sum += ary[i]*(n-1-ary[i]);
}
sum /= 2;
printf("%.3lf\n",1.0-sum*1.0/((n*(n-1)*(n-2))/6));
}
return 0;
}
威威貓系列故事——籃球夢
Time Limit : 300/100ms (Java/Other)Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 3Accepted Submission(s) : 1
Problem Description 威威貓十分迷戀籃球比賽，是忠實的NBA球迷，他常常幻想自己那肥碩的身軀也能飛起扣籃。另外，他對籃球教練工作也情有獨鐘，特別是對比賽的戰術，投籃選擇方面也是很有研究，下面就是威威貓研究過的一個問題：
一場NBA籃球比賽總共48分鐘，假如我們現在已經知道當前比分 A:B，A代表我方的比分，B代表對方的比分，現在比賽還剩下t秒時間。我們簡單的認為雙方各自進攻一次的時間皆固定為15秒（不到15秒則進攻不得分），且為交替進攻，即我方進攻一次，接著對方進攻，依次循環。
進攻有三種選擇方式：（這裡不考慮命中率）
1、造犯規，（假設都兩罰一中）得1分；
2、中距離投籃 得2分；
3、三分球 得3分。
為了簡化問題，假設在對方回合，由於我方防守比較好，只讓對手得1分，且為固定，即對方的進攻回合就為每回合得1分。現在比賽進入最後關頭，接下來第一個回合是我方進攻，現在威威貓想要知道教練有多少種不同的選擇能使我方可能贏得比賽（可能的意思就是不考慮命中率的情況）。
Input 輸入有多組數據（不超過250組）； 每組數據包含3個整數A，B和t，其中A和B 表示當前的比分（0 <= A, B <= 200），t表示還剩多少時間（單位秒 0 <= t <= 600）。
Output 請輸出可行的方案數，每組數據輸出占一行。
Sample Input
88 90 50
Sample Output
6 [hint] 樣例解析： 當前比分是88：90，還剩50秒則對方還最多有一次進攻機會（最後5秒進攻不成功），我方有兩次，對方的最終得分將是91， 我方至少在兩回合中拿到4分才能勝利，所以所有方案數是6種，即： 第一球 第二球 1 3 2 2 2 3 3 1 3 2 3 3 [/hint]
Source 動態規劃
#include
#include
#include
using namespace std;
int main()
{
int i,j,k,kk;
int N;
int t;
int a,b,w;
int cnt,n;
int ary[1005];
int sum;
scanf("%d",&N);
while(N-- && scanf("%d",&n))
{
for(i=1,sum=0;i<=n;i++)
{
scanf("%d",&ary[i]);
sum += ary[i]*(n-1-ary[i]);
}
sum /= 2;
printf("%.3lf\n",1.0-sum*1.0/((n*(n-1)*(n-2))/6));
}
return 0;
}
