paulinsider's website

硬币问题

dandan — Thu, 01 Nov 2012 14:05:16 GMT

【题目描述】

有 n 种硬币，面值分别为 v1, v2.....vn ，每种都有无限多。给定非负整数 S ，可以选用多少个硬币，使得面值之和恰好为 S ？输出硬币数目的最小值和最大值。

【输入格式】

第一行两个整数 n, S (1 < n < 100, 0 < S < 100000)。

第二行 n 个整数 v{i=1..n} (1 < vi < S) 。

【输出格式】

第一行两个整数，分别表示硬币数目的最小值 a 和最大值 b 。无解则输出 -1 。

第二行 a 个整数分别表示使用的是第几种硬币。

第三行 b 个整数分别表示使用的是第几种硬币。

【样例输入】

6 12 
 1 2 3 4 5 6

【样例输出】

2 12 
 6 6 
 1 1 1 1 1 1 1 1 1 1 1 1

【提示】

样例是特殊的，编号和面值是相同的。你编写程序的时候要注意输出编号而不是面值。

结果按编号升序输出。

若有多组解，输出字典序小的。

【来源】

算法竞赛入门经典例题 9-3

题解：

本题是一个较水的动态规划，主要是输出路径还有点难度。对于每个状态记录其的父节点。。没了，就是这么简单。

代码：

C++语言:

made by PaulInsider!
#include #include #include #include #include using namespace std;
vector<int>ans;
int n,m,w[200];
int q[100005][2]={0},a[100005][2]={0};
int main()
{
freopen ("kouka.in","r",stdin);
freopen ("kouka.out","w",stdout);
cin>>n>>m;
for (int i=1;i<=n;i++)
{
cin>>w[i];
}
for (int i=0;i<=m;i++)
{
q[i][0]=99999;
q[i][1]=99999;
a[i][0]=-1;
a[i][1]=-1;
}
q[0][0]=0;
for (int i=1;i<=m;i++)
{
for (int j=0;j<=n;j++)
{
if (i-w[j]>=0&&q[i][0]>q[i-w[j]][0]+1)
{
q[i][0]=q[i-w[j]][0]+1;
q[i][1]=j;
}
}
}
a[0][0]=0;
for (int i=1;i<=m;i++)
{
for (int j=1;j<=n;j++)
{
if (i-w[j]>=0&&a[i-w[j]][0]!=-1&&a[i-w[j]][0]+1>a[i][0])
{
a[i][0]=a[i-w[j]][0]+1;
a[i][1]=j;
}
}
}
cout<<q[m][0]<<' '<<a[m][0]<<endl;
int tmp;
tmp=m;
while (q[tmp][1]!=99999)
{
ans.push_back(q[tmp][1]);
tmp=tmp-w[q[tmp][1]];
}
sort(ans.begin(),ans.end());
for (int i=0;i<ans.size();i++)
cout<<ans[i]<<' ';
cout<<endl;
tmp=m;
ans.clear();
while (a[tmp][1]!=-1)
{
ans.push_back(a[tmp][1]);
tmp=tmp-w[a[tmp][1]];
}
sort(ans.begin(),ans.end());
for (int i=0;i<ans.size();i++)
cout<<ans[i]<<' ';
return 0;
}

多米诺骨牌

dandan — Thu, 01 Nov 2012 12:50:37 GMT

【问题描述】

多米诺骨牌有上下2个方块组成，每个方块中有1~6个点。现有排成行的n个多米诺骨牌如图8-1所示。

编程用最少的旋转次数使多米诺骨牌上下2行点数之差达到最小。上方块中点数之和记为sum1，下方块中点数之和记为sum2，它们的差为|sum1-sum2|。例如在图8-1中，sum1=6+1+1+1=9，sum2=1+5+3+2=11，|sum1-sum2|=2。每个多米诺骨牌可以旋转180°，使得上下两个方块互换位置。

对于图8-1中的例子，只要将最后一个多米诺骨牌旋转180°，可使上下2行点数之差为0。

【输入】

输入文件的第一行是一个正整数n(1≤n≤1000)，表示多米诺骨牌数。接下来的n行表示n个多米诺骨牌的点数。每行有两个用空格隔开的正整数，表示多米诺骨牌上下方块中的点数a和b，且1≤a，b≤6。

【输出】

输出文件仅一行，包含一个整数。表示求得的最小旋转次数。

【样例】

dom.in

6 1

1 5

1 3

1 2

dom.out

题解：

本题是一个简单的背包型动态规划。背包型动态规划是一件物品要或不要，而在这里头是，该骨牌是否翻转。。故转移方程为q[i][j]=min(q[i-1][j-w[i][0]],q[i-1][j-w[i][1]]+1);

q[i][j]表示前i个骨牌上面的数字之和为j的最小翻转次数。。w[i][0]，w[i][1]表示i骨牌上下的数字。。很简单。要想剪枝的话。可以开一个记录前i个骨牌数字和的数组。每回枚举在0~sum[i]之间。。。

代码：

C++语言:

made by PaulInsider!
#include #include #include using namespace std;
int n,w[1005][2]={0},ssum=0,answer,ans=9999999;
int q[1005][6005],sum[1005]={0};
int abs(int x)
{
if (x>=0)
return x;
else
return 0-x;
}
int main()
{
freopen ("dom.in","r",stdin);
freopen ("dom.out","w",stdout);
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>w[i][0]>>w[i][1];
sum[i]=sum[i-1]+max(w[i][0],w[i][1]);
ssum+=(w[i][0]+w[i][1]);
}
for (int i=0;i<=n;i++)
{
for (int j=0;j<=ssum;j++)
{
q[i][j]=99999;
}
}
q[0][0]=0;
for (int i=1;i<=n;i++)
{
for (int j=sum[i];j>=0;j--)
{
if (j-w[i][0]>=0&&q[i-1][j-w[i][0]]<q[i][j])
{
q[i][j]=q[i-1][j-w[i][0]];
}
if (j-w[i][1]>=0&&q[i-1][j-w[i][1]]+1<q[i][j])
{
q[i][j]=q[i-1][j-w[i][1]]+1;
}
if (i==n)
{
if (abs(ssum-j*2)<ans&&q[i][j]!=99999)
{
ans=abs(ssum-j*2);
answer=q[i][j];
}
}
}
}
cout<<answer<<endl;
return 0;
}

[Tyvj 1965] 汪星人入侵

dandan — Thu, 01 Nov 2012 10:11:07 GMT

【题目背景】

（Rainbow和Freda正在城堡里玩得开心的时候，外面传来一阵声音：小猫乖乖，把门开开~）
Rainbow：不好！是汪星人入侵！
Freda：肿么办肿么办T_T？
Rainbow：我们先躲起来观察一下汪星人的动态吧>_<！

【题目描述】

Rainbow和Freda躲到了瞭望塔里，发现汪星人这次的目标有些奇怪。
Rainbow的城堡有N扇门，从1到N标号，它们初始时都是关着的。现在来了N只汪星人，第i只汪星人会把所有标号能被i整除的门的状态改变（即把标号能被i整除的关着的门打开，把标号能被i整除的开着的门关上）。
Rainbow为城堡定义了一个不安全指数——即最后打开着的门的数目。Rainbow想请你帮忙计算，城堡的不安全指数是多少？

【输入格式】

每个测试点包括多组测试数据。
第一行一个整数T，表示一共有T组测试数据。
接下来T行每行一个整数N，表示Rainbow城堡的门的数量。

【输出格式】

输出T行，第i行的数字表示，对于第i个N，城堡的不安全指数。

【样例输入】

【样例输出】

【提示】

样例解释:　　　
当N=4的时候，4扇门情况如下（1表示开，0表示关）：
没有汪星人来的时候：0000
第一只汪星人来后：1111
第二只汪星人来后：1010
第三只汪星人来后：1000
第四只汪星人来后：1001
所以答案为2
对于20%的数据，T<=100.
对于100%的数据，T<=20000，N<=50000.

解题报告：

本题我看到后没什么思路，果断模拟。不过，模拟也需要一个技巧，那就是，第i个人一定只能开关i以后的门。这样，我们就可以开一个记录门开关的数组，将50000个人开关门以后各个门的开关情况记录下来。这样开一个ans数组记录答案。。

代码：

C++语言:

made by PaulInsider!
#include #include #include using namespace std;
int q[50005]={0};
bool used[50005]={0};
int n,m;
int main()
{
freopen ("wang.in","r",stdin);
freopen ("wang.out","w",stdout);
for (int i=2;i<=50000;i++)
{
for (int j=i;j<=50000;j+=i)
{
used[j]=!used[j];
}
}
for (int i=1;i<=50000;i++)
{
q[i]=q[i-1]+(!used[i]);
}
cin>>n;
for (int i=0;i<n;i++)
{
cin>>m;
cout<<q[m]<<endl;
}
return 0;
}

[Poetize 9] 升降梯上

dandan — Wed, 31 Oct 2012 03:41:14 GMT

【题目描述】

开启了升降梯的动力之后，探险队员们进入了升降梯运行的那条竖直的隧道，映入眼帘的是一条直通塔顶的轨道、一辆停在轨道底部的电梯、和电梯内一杆控制电梯升降的巨大手柄。
Nescafe之塔一共有N层，升降梯在每层都有一个停靠点。手柄有M个控制槽，第i个控制槽旁边标着一个数Ci，满足C10，表示手柄扳动到该槽时，电梯将上升Ci层；如果Ci<0，表示手柄扳动到该槽时，电梯将下降-Ci层；并且一定存在一个Ci=0，手柄最初就位于此槽中。注意升降梯只能在1~N层间移动，因此扳动到使升降梯移动到1层以下、N层以上的控制槽是不允许的。
电梯每移动一层，需要花费2秒钟时间，而手柄从一个控制槽扳到相邻的槽，需要花费1秒钟时间。探险队员现在在1层，并且想尽快到达N层，他们想知道从1层到N层至少需要多长时间？

【输入格式】

第一行两个正整数N、M。
第二行M个整数C1、C2……CM。

【输出格式】

输出一个整数表示答案，即至少需要多长时间。若不可能到达输出-1。

【样例输入】

6 3 
 -1 0 2

【样例输出】

【提示】

手柄从第二个槽扳到第三个槽（0扳到2），用时1秒，电梯上升到3层，用时4秒。
手柄在第三个槽不动，电梯再上升到5层，用时4秒。
手柄扳动到第一个槽（2扳到-1），用时2秒，电梯下降到4层，用时2秒。
手柄扳动到第三个槽（-1扳倒2），用时2秒，电梯上升到6层，用时4秒。
总用时为(1+4)+4+(2+2)+(2+4)=19秒。

对于30% 的数据，满足1≤N≤10，2<=M<=5。
对于 100% 的数据，满足1≤N≤1000，2<=M<=20

题解：

本题较水，可以说很水，但是刚开始E了。。重写一遍后AC，其实，和迷之阶梯差不多，按照SPFA的思路搜索，从1开始，按照每个档位一次是，开一个ans的二维数组记录在K层时，档位是J时的最优值，每回如果比最优值优就更新。。反之不更新。。。

代码：

C++语言:

made by PaulInsider!
#include #include #include #include using namespace std;
int n,m,w[30],ans[1005][30],tou,flo,tmp,use,answer=999999;
struct hehe
{
int ceng,num,number;
}temp;
queue<hehe>q;
int aabs(int x)
{
if (x>=0)
return x;
else
return 0-x;
}
void bfs();
int main()
{
freopen ("updown.in","r",stdin);
freopen ("updown.out","w",stdout);
cin>>n>>m;
for (int i=1;i<=m;i++)
{
cin>>w[i];
if (w[i]==0)
{
tou=i;
}
for (int j=0;j<=n;j++)
{
ans[j][i]=999999;
}
}
bfs();
for (int i=1;i<=m;i++)
{
if (answer>ans[n][i])
answer=ans[n][i];
}
if (answer==999999)
cout<<-1;
else
cout<<answer;
return 0;
}
void bfs()
{
temp.ceng=1;
temp.num=tou;
temp.number=0;
q.push(temp);
ans[1][tou]=0;
while (!q.empty())
{
for (int i=1;i<=m;i++)
{
flo=q.front().ceng+w[i];
tmp=aabs(q.front().num-i);
use=tmp+abs(w[i])*2;
if (flo>0&&flo<=n&&ans[flo][i]>q.front().number+use)
{
ans[flo][i]=q.front().number+use;
temp.ceng=flo;
temp.num=i;
temp.number=ans[flo][i];
q.push(temp);
}
}
q.pop();
}
}

[Tyvj Aug11] 黄金矿工

dandan — Tue, 30 Oct 2012 09:18:38 GMT

描述 Description

黄金矿工是一个经典的小游戏，它可以锻炼人的反应能力。该游戏中，可以通过"挖矿”获得积分并不断升级。玩家可以在线玩flash版黄金矿工，也可以下载后玩单机版黄金矿工。目前，黄金矿工小游戏有多个版本，例如黄金矿工双人版，黄金矿工单人版等。
Jimmy是一位黄金矿工，他所在的金矿是一个n*n的矩形区域（俯视），区域内有黄金、石头和TNT，由一个n*n的矩阵描述。黄金的价值对应矩阵中的正值，石头的价值对应矩阵中的负值，TNT由0表示。换句话说，挖到黄金赚钱，石头亏损，如果挖到TNT就挂了~_~

Jimmy租到的挖矿工具很特别，它的形状是一个长宽任意（均为正整数）的矩形，可以取走被该工具覆盖的矩形区域内的所有物品，但如果该区域内有TNT，该工具将被炸毁，此时Jimmy将不得不赔偿矿主+∞元！！！需要注意的是，该工具只能在金矿范围内使用（即不得超出金矿边界），且租金为每次使用十元。
现在，Jimmy想知道，如果他至多只有一次租用该工具的机会，他能获得的最大收益是多少。当然，如果Jimmy租用该工具无论如何都会亏损，他可以不租用，此时收益为0.

输入格式 Input Format

第一行：一个整数n
接下来n行，每行n个整数（绝对值<100），为题目中所描述的矩阵。

输出格式 Output Format

一个数，即Jimmy所能获得的最大收益。

样例输入 Sample Input

0 -1 -1

0 -12 0

-19 0 0

样例输出 Sample Output

数据范围和注释 Hint

样例解释：
无论Jimmy怎么挖矿，挖到的不是石头，就是TNT，总之无论如何都会亏损，所以选择不租用工具，收益为0

数据范围：
对于30%的数据：0对于60%的数据：0对于100%的数据：0

题解：

本题是一道关于最大子矩阵和的动态规划题，也是本弱菜第一次接触，但由于网上的一篇关于最大子矩阵和的PPt，把我给坑住了。。所以，自己遇到题要好好想想，不要被一些弱爆的PPt坑掉。。。

本题的状态时q[i][j]。。i,j表示第i行到第j行这区间的最大子矩阵和。这样就可以将本题转化为区间最大和问题。。预处理w[i][j]为以i,j为端点和以（0,0）为端点的矩形的值。很好处理。。呵呵，说到这应该就简单了。。注意有一点，就是，值为0的店是TNT，不能要。多亏Yeefan Zhu的提醒，可以将该点置为负无穷。。简单易用。。

上代码：

C++语言:

made by PaulInsider!
#include #include #include using namespace std;
long long n,w[400][400]={0},a,q[400][400]={0},answer=0,ans=0,tmp;
int main()
{
freopen ("miner.in","r",stdin);
freopen ("miner.out","w",stdout);
cin>>n;
for (int o=1;o<=n;o++)
{
for (int p=1;p<=n;p++)
{
cin>>a;
if (a==0)
a=-100000000;
w[o][p]=w[o-1][p]+w[o][p-1]-w[o-1][p-1]+a;
}
}
for (int i=1;i<=n;i++)
{
for (int j=i;j<=n;j++)
{
ans=w[j][0]-w[i-1][0];
q[i][j]=w[j][0]-w[i-1][0];
for (int k=1;k<=n;k++)
{
tmp=w[j][k]-w[i-1][k];
if (tmp-ans>q[i][j])
q[i][j]=tmp-ans;
if (tmp<ans)
ans=tmp;
}
if (q[i][j]>answer)
answer=q[i][j];
}
}
if (answer<=10)
cout<<0;
else
cout<<answer-10;
return 0;
}

[Nescafé 20] 玉蟾宫

dandan — Tue, 30 Oct 2012 01:10:46 GMT

【背景】

有一天，小猫rainbow和freda来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。

【题目描述】

这片土地被分成N*M个格子，每个格子里写着'R'或者'F'，R代表这块土地被赐予了rainbow，F代表这块土地被赐予了freda。
现在freda要在这里卖萌。。。它要找一块矩形土地，要求这片土地都标着'F'并且面积最大。
但是rainbow和freda的OI水平都弱爆了，找不出这块土地，而蓝兔也想看freda卖萌（她显然是不会编程的……），所以它们决定，如果你找到的土地面积为S，它们每人给你S两银子。

【输入格式】

第一行两个整数N,M，表示矩形土地有N行M列。
接下来N行，每行M个用空格隔开的字符'F'或'R'，描述了矩形土地。

【输出格式】

输出一个整数，表示你能得到多少银子，即(3*最大'F'矩形土地面积)的值。

【样例输入】

5 6 
 R F F F F F 
 F F F F F F 
 R R R F F F 
 F F F F F F 
 F F F F F F

【样例输出】

【提示】

各个测试点1s

对于50%的数据，1<=N,M<=200
对于100%的数据，1<=N,M<=1000

题解：

本题是一个练习单调堆栈的题，也是本人第一次写单调堆栈，在某天的晚上看完官方题解，想着想着睡着了。。。（当时认为官方题解有问题），后来在第二天早上买饭去机房的路上顿悟。。。其实不难，呵呵。先上官方题解，如若看懂则不必要往后看。

官方题解：

们先来考虑这样一个问题，水平线上有一些宽度为1，高度不定的阴影区域，要求找到包含在这个区域内的一个矩形，使得矩形面积最大。

如图所示，高度不一的柱形条就是阴影区域，不同颜色框出的矩形都满足要求，其中红色矩形的面积最大。

维护一个栈中元素高度单调递增的栈，初始化栈中第一个元素高度宽度均为0。

然后每次读入一个矩形，若它比栈顶元素还高就直接进栈；

否则不断将栈中元素弹栈，直到当前栈顶元素能够与读入的矩形满足高度递增。

弹栈过程中累加弹出的元素的宽度，然后每弹出一个就判断（当前弹出元素的高度×累加的宽度）能否更新最大面积ans。

然后以新的矩形高度作高，刚才弹出栈的元素总宽度加上新矩形宽度作宽，把这个矩形插入到栈里。

最终栈肯定是一个单调的，只需要再把栈一个个弹空，弹栈过程中仍像上面那样计算即可。

这个算法的时间复杂度是O(n)的。

在本题中，我们只需要枚举每一行以上的'F'作为阴影区域，用上述单调栈算法求一遍最大矩形面积即可。时间复杂度O(NM)。

说实话，鄙人的理解能力不是很强，看完后基本上一点都不懂。。。后来想想，其实就是将这个矩阵变成了N个矩阵。（一每一行为底边的矩阵），在按照上面的思路做。

在我的程序里，w[i][j]表示第j列向上的i个土地中连续为F的个数。这就相当于一个个矩形，每一行都有j个矩形，这样枚举每一行，按照官方的方法一遍一遍找就行了。

源程序：

C++语言:

made by PaulInsider!
#include
#include
#include
#include
using namespace std;
int n,m,w[1005][1005]={0},answer=0;
char a;
int q[1005]={0},num,weight,high,t[1005];
int main()
{
freopen ("jademoon.in","r",stdin);
freopen ("jademoon.out","w",stdout);
cin>>n>>m;
for (int o=1;o<=n;o++)
{
for (int p=1;p<=m;p++)
{
cin>>a;
if (a=='R')
continue;
w[o][p]=w[o-1][p]+1;
}
}
for (int i=1;i<=n;i++)
{
memset(q,0,sizeof(q));
q[0]=-1;num=0;
memset(t,0,sizeof(t));
for (int j=1;j<=m;j++)
{
weight=0;high=w[i][j];
while (high<q[num])
{
weight+=t[num];
if (weight*q[num]>answer)
answer=weight*q[num];
num--;
}
num++;
q[num]=high;
t[num]=weight+1;
}
weight=0;
while (num)
{
weight+=t[num];
if (weight*q[num]>answer)
answer=weight*q[num];
num--;
}
}
cout<<3*answer;
return 0;
}

遇到瓶颈。。。

dandan — Tue, 23 Oct 2012 03:42:02 GMT

求各路神牛帮忙破镜。。。。

韩国明星后续之字典树写法！

dandan — Thu, 10 Nov 2011 08:52:48 GMT

C++语言:

made by PaulInsider!
#include #include #include #include using namespace std;
int n,m;
int find();
char str[128];
int cmp(const void*a,const void *b);
struct tree
{
    int num;
    tree *s[128];
};
struct hehe
{
    int mark;
    char st[128];
}q[100001];
int main()
{
    freopen ("star.in","r",stdin);
    freopen ("star.out","w",stdout);
    scanf("%d\n",&n);
    tree *head=new tree;
    for (int p=0;p<128;p++)
    {
        head->s[p]=NULL;
    }
    for (int i=0;i<n;i++)
    {
        q[i].mark=0;
        scanf("%[^\n]\n",&q[i].st);
        int lq;
        lq=strlen(q[i].st);
        tree *p=new tree;
        p=head;
        for (int j=0;j<lq;j++)
        {
            if (j==lq-1)
            {
                p->num=i;
                break;
            }
            if (p->s[q[i].st[j]-'0']==NULL)
            {
                tree *b=new tree;
                for (int u=0;u<128;u++)
                {
                    b->s[u]=NULL;
                }
                p->s[(q[i].st[j])-'0']=b;
                b=NULL;
                delete b;
            }
            p=p->s[q[i].st[j]-'0'];
        }
        p=NULL;
        delete p;
    }
    scanf("%d\n",&m);
    for (int i=0;i<m;i++)
    {
        char str[128];
        scanf("%[^\n]\n",&str);
        int lw;
        lw=strlen(str);
        int tmp;
        scanf("%d\n",&tmp);
        int temp;
        tree *p=new tree;
        p=head;
        for (int j=0;j<lw;j++)
        {
            if(j==lw-1)
            {
                temp=p->num;
            }
            p=p->s[str[j]-'0'];
        }
        q[temp].mark+=tmp;
    }
    qsort(q,n,sizeof(q[0]),cmp);
    for (int i=0;i<n;i++)
    {
        cout<<q[i].st<<endl<<q[i].mark<<endl;
    }
    return 0;
}
int cmp(const void *a,const void *b)
{
    struct hehe*c=(struct hehe*)a;
    struct hehe *d=(struct hehe*)b;
    return d->mark - c->mark;
}

韩国明星（解题报告+原程）

dandan — Thu, 10 Nov 2011 07:10:50 GMT

【问题描述】

　　在LazyCat同学的影响下，Roby同学开始听韩国的音乐，并且越来越喜欢H.o.T，尤其喜欢安七炫和Tony，可是，爱学习爱思考的Roby同学想，如果以后喜欢的韩星越来越多怎么办呢？Roby怎么知道Roby最喜欢谁呢（Roby都不知道谁知道呢。。。。）？
　　于是，Roby同学求助于你。
　　 Roby首先会给你一张表，表上是所有他认识的韩星的名字，一开始他对所有韩星的好感度都为0。
　　然后Roby会告诉你一些他对某个韩星的好感度变化。
　　最后，请按照Roby对他们好感从大到小的顺序输出他们。

[输入]
　　第一行一个个数N，表示Roby知道的韩星数目。
　　后面有N行，表示每一个Roby认识的韩星的名字。
　　再下面一行一个数K。
　　接下来2K行，每两行为一组，上面一行为韩星的名字Name，下面一行为好感度变化量Change。

[输出]
　　 N2行，依据韩星们的受Roby好感度从大到小的顺序输出，每两行为一组，第一行输出韩星的名字，第二行输出受Roby的好感度。
[样例输入]
　　 3
　　 HhIsaGay
　　 ZcLoveStudy
　　 OneBlueOne
　　 5
　　 ZcLoveStudy
　　 100
　　 OneBlueOne
　　 8888
　　 ZcLoveStudy
　　 20
　　 OneBlueOne
　　 8888
　　 HhIsaGay
　　 -1000

[样例输出]
　　 OneBlueOne
　　 17776
　　 ZcLoveStudy
　　 120
　　 HhIsaGay
　　 -1000
[数据范围]
　　对于20%的数据，保证N<=100，K<=100.
　　对于40%的数据，保证N<=10000，K<=30000.
　　对于100%的数据，保证N<=100000　-8888<=Change<=8888　K<=100000.
[时限]
　　 2S

题解：

本题属于字符串处理题，如果用单纯的模拟是绝对超时的，因为有100000组数据，呵呵，转念一想，也就是查找给的那个人是费时间，所以我采取了二分查找的方法，速度一流，呵呵，上代码！！

原程：C++语言: Codee#23888
#include
#include
#include
#include
using namespace std;
int n,m;
int find();
char str[100];
int cmp1(const void*a,const void *b);
int cmp2(const void *a,const void *b);
struct hehe
{
    int mark;
    char s[100];
}q[100001];
int main()
{
    freopen ("star.in","r",stdin);
    freopen ("star.out","w",stdout);
    scanf("%d\n",&n);
    for (int i=0;i<n;i++)
    {
        scanf("%[^'\n]\n",&q[i].s);
        q[i].mark=0;
    }
    qsort(q,n,sizeof(q[0]),cmp1);
    scanf("%d\n",&m);
    for (int i=0;i<m;i++)
    {
        scanf("%[^\n]\n",&str);
        int temp;
        temp=find();
        int tmp;
        scanf("%d\n",&tmp);
        q[temp].mark+=tmp;
    }
    qsort(q,n,sizeof(q[0]),cmp2);
    for (int i=0;i<n;i++)
    {
        cout<<q[i].s<<endl<<q[i].mark<<endl;
    }
    return 0;
}
int cmp1(const void*a,const void *b)
{
    struct hehe*c=(struct hehe*)a;
    struct hehe*d=(struct hehe*)b;
    return strcmp(c->s,d->s);
}
int find()
{
    int l=0;
    int r,mid;
    r=n -1;
    mid=((l+r)>>1);
    while (l<r)
    {
        if (l==r)
            return l;
        else
        {
            if (strcmp(q[mid].s,str)<0)
            {
                l=mid+1;
                mid=((l+r)>>1);
                continue;
            }
            if (strcmp(q[mid].s,str)==0)
            {
                return mid;
            }
            if (strcmp(q[mid].s,str)>0)
            {
                r=mid-1;
                mid=((l+r)>>1);
                continue;
            }
        }
    }
    return l;
}
int cmp2(const void *a,const void *b)
{
    struct hehe *c=(struct hehe*)a;
    struct hehe *d=(struct hehe*)b;
    return d->mark - c->mark;
}

堆排序（以合并果子为例）

dandan — Wed, 09 Nov 2011 14:29:07 GMT

堆：

我感觉着就是维护和建堆小困难，本人第一次写堆今天，代码很长，唉，日后会发一些后续代码，发上代码吧！
C++语言:

made by PaulInsider!
#include #include #include using namespace std;
int n,heap[10001],answer=0;
void weihu(int x);
void swap(int x,int y);
int main()
{
    freopen ("fruit.in","r",stdin);
    freopen ("fruit.out","w",stdout);
    scanf("%d",&n);
    for (int p=1;p<=n;p++)
    {
        scanf("%d",&heap[p]);
    }
    for (int j=(n>>1);j>=1;j--)
    {
        weihu(j);
    }
    while (1)
    {
        if (n==1)
        {
            break;
        }
        answer+=heap[1];
        if (3<=n)
        {
            if (heap[2]>heap[3])
            {
                answer+=heap[3];
                heap[1]+=heap[3];
                heap[3]=heap[n];
                n--;
                weihu(3);
                weihu(1);
            }
            else
            {
                answer+=heap[2];
                heap[1]+=heap[2];
                heap[2]=heap[n];
                n--;
                weihu(2);
                weihu(1);
            }
        }
        else
        {
            answer+=heap[2];
            heap[1]+=heap[2];
            heap[2]=heap[n];
            n--;
            weihu(2);
            weihu(1);
        }
    }
    cout<<answer;
    return 0;
}
void weihu(int x)
{
    int temp;
    temp=heap[x];
    int i;
    i=x;
    while (i<=n)
    {
        int a,b;
        a=(i<<1);
        b=(i<<1)+1;
        if (a>n)
        {
            break;
        }
        else
        {
            if (b>n)
            {
                if (heap[a]<heap[i])
                {
                    swap(a,i);
                    i=a;
                    continue;
                }
                else
                {
                    break;
                }
            }
            else
            {
                if (heap[a]<heap[b])
                {
                    if (heap[a]<heap[i])
                    {
                        swap(a,i);
                        i=a;
                    }
                    else
                    {
                        if (heap[a]==heap[i])
                        {
                            break;
                        }
                        if (heap[a]>heap[i])
                        {
                            break;
                        }
                    }
                }
                else
                {
                    if (heap[b]<heap[i])
                    {
                        swap(b,i);
                        i=b;
                    }
                    else
                    {
                        if (heap[b]==heap[i])
                        {
                            break;
                        }
                        if (heap[b]>heap[i])
                        {
                            break;
                        }
                    }
                }
            }
        }
    }
}
void swap(int x,int y)
{
    int temp;
    temp=heap[x];
    heap[x]=heap[y];
    heap[y]=temp;
}

有点长，神牛飘过，水牛留步！

paulinsider's website

硬币问题

【题目描述】

【输入格式】

【输出格式】

【样例输入】

【样例输出】

【提示】

【来源】

多米诺骨牌

[Tyvj 1965] 汪星人入侵

【题目背景】

【题目描述】

【输入格式】

【输出格式】

【样例输入】

【样例输出】

【提示】

[Poetize 9] 升降梯上

【题目描述】

【输入格式】

【输出格式】

【样例输入】

【样例输出】

【提示】

[Tyvj Aug11] 黄金矿工

[Nescafé 20] 玉蟾宫

【背景】

【题目描述】

【输入格式】

【输出格式】

【样例输入】

【样例输出】

【提示】

遇到瓶颈。。。

韩国明星后续之字典树写法！

韩国明星（解题报告+原程）

堆排序（以合并果子为例）

堆：

我感觉着就是维护和建堆小困难，本人第一次写堆今天，代码很长，唉，日后会发一些后续代码，发上代码吧！C++语言:

我感觉着就是维护和建堆小困难，本人第一次写堆今天，代码很长，唉，日后会发一些后续代码，发上代码吧！
C++语言: