SCAU 周训一

A - A HDU - 2544

1.题目描述：
在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？

Input
输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。

Output
对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间

Sample Input
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0

Sample Output
3
2

2.题意：
题目意思很明显了吧，抽象一下就是有N个点，有M条边组成的无向图，求1到N的最短路径。

3.思路：
既然抽象成了图的问题那么就是著名的：最短路径问题。解决这个问题有个非常好用的方法——基于贪心的Dijkstra算法。它解决的是：单源到任意点的最短路径问题。

4.代码：

//A
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int INF = 0x3f3f3f;
const int MAX_N = 100+5;
const int MAX_M = 10000+5;
int map[MAX_N][MAX_N];
int dis[MAX_N];
bool vis[MAX_N];
int N,M,tmp,x,y;
void dijkstra(int s,int e)
{for(int i=1;i<=N;++i){dis[i]=map[s][i];vis[i]=0;}dis[s]=0;vis[s]=1;int min,k;for(int i=1;i<=N;++i){min=INF;for(int j=1;j<=N;++j)if(!vis[j]&&dis[j]<min){k=j;min=dis[j];}vis[k]=1;for(int j=1;j<=N;++j)if(dis[j]>dis[k]+map[k][j])dis[j]=dis[k]+map[k][j];}cout<<dis[e]<<endl;
}
int main()
{//freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);while(cin>>N>>M&&N&&M){for(int i=1;i<=N;++i)for(int j=1;j<=N;++j)if(i==j) map[i][j]=0;else map[i][j]=INF;for(int i=0;i<M;++i){cin>>x>>y>>tmp;if(tmp<map[x][y]){map[x][y]=tmp;map[y][x]=tmp;}}dijkstra(1,N);}return 0;
}

B - B CSU - 1803

1.题目描述：
给出正整数 n 和 m，统计满足以下条件的正整数对 (a,b) 的数量：

1. 1≤a≤n,1≤b≤m;
2. a×b 是 2016 的倍数。
   Input

输入包含不超过 30 组数据。
每组数据包含两个整数 n,m (1≤n,m≤10 9).

Output
对于每组数据，输出一个整数表示满足条件的数量。
Sample Input
32 63
2016 2016
1000000000 1000000000

Sample Output
1
30576
7523146895502644

2.题意：
略

3.思路：
同余定理：(a * b)%2016 <=> (a%2016) * (b%2016)%2016
那么我们只关心：1-2016之内的余数乘起来取余2016是不是等于0即可。
假设余数为i在n中有a[i]个，在m中有b[i]个，sum（a[i] * b[j]）( 2016 | i*j )
（PS：相乘是因为前面有a[i]种可能性（就是a[i]个i的倍数）乘以后面b[i]个可能性（就是b[i]个i的倍数））
4.代码：

//B
#include<iostream>
#include<cstdio>
#include<cstring>
#define FAST ios::sync_with_stdio(false)
using namespace std;
long long a[2016],b[2016];
int main()
{//freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);int n,m;while(~scanf("%d%d",&n,&m)){long long ans=0;for(int i=0;i<2016;++i)a[i]=n/2016,b[i]=m/2016;for(int i=1;i<=n%2016;++i) a[i]++;for(int i=1;i<=m%2016;++i) b[i]++;for(int i=0;i<2016;++i)for(int j=0;j<2016;++j)if(!(i*j%2016))ans+=a[i]*b[j];cout<<ans<<endl;}return 0;
}

C - C HackerRank - max-min-difference

1.题目描述：

2.题意：
去掉一个值，使得最大值与最小值的差最小。

3.思路：
这个签到题，主要是记录最大值，次大值，最小值，次小值。然后分类讨论。（不要问我为啥这么复杂的实现，脑抽…QAQ）

4.代码：

//C
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#define FAST ios::sync_with_stdio(false)
using namespace std;
map<int,bool> m;
int main()
{//freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);int n,tmp;cin>>n;for(int i=0;i<n;++i){cin>>tmp;if(m.count(tmp))m[tmp]=false;elsem[tmp]=true;}map<int,bool>::iterator it,Max,Min;map<int,bool>::iterator last_max,last_min;bool flag1=true,flag2=true;for(it=m.begin();it!=m.end();++it){if(flag1){Min=it;flag1=0;}else if(flag2){last_min=it;flag2=0;}//cout<<"list m :"<<it->first<<" "<<it->second<<endl;}Max=--it;last_max=--it;//cout<<Max->first<<" "<<Min->first<<endl;//cout<<last_max->first<<" "<<last_min->first<<endl;if(Min->second&&!Max->second) cout<<Max->first - last_min->first<<endl;else if(Max->second&&!Min->second) cout<<last_max->first - Min->first<<endl;else if(Max->second&&Min->second) cout<<min(Max->first - last_min->first,last_max->first - Min->first)<<endl;else cout<<Max->first - Min->first<<endl;return 0;
}

D - D HDU - 5965

1.题目描述：
扫雷游戏是晨晨和小璐特别喜欢的智力游戏，她俩最近沉迷其中无法自拔。
该游戏的界面是一个矩阵，矩阵中有些格子中有一个地雷，其余格子中没有地雷。 游戏中，格子可能处于己知和未知的状态。如果一个己知的格子中没有地雷，那么该 格子上会写有一个一位数，表示与这个格子八连通相邻的格子中地雷总的数量。
现在，晨晨和小璐在一个3行N列（均从1开始用连续正整数编号）的矩阵中进 行游戏，在这个矩阵中，第2行的格子全部是己知的，并且其中均没有地雷；而另外 两行中是未知的，并且其中的地雷总数量也是未知的。
晨晨和小璐想知道，第1行和第3行有多少种合法的埋放地雷的方案。

Input
包含多组测试数据，第一行一个正整数T，表示数据组数。
每组数据由一行仅由数字组成的长度为N的非空字符串组成，表示矩阵有3行N 列，字符串的第i个数字字符表示矩阵中第2行第i个格子中的数字。
保证字符串长度N <= 10000，数据组数<= 100。

Output
每行仅一个数字，表示安放地雷的方案数mod100,000,007的结果。

Sample Input
2
22
000

Sample Output
6
1

2.题意：
略

3.思路：
这题看一眼知道是动态规划，但是真的不知道怎么写，后来查了很久，终于有点感觉，然后对着别人的代码debug了好久…（重做预定），想到dp其实很简单，因为前后的联系很密切，但是怎么写dp呢，这就很难了。我们发现，我们第二行能够作用的范围是在左右和自己列，那么前面的放置决定了后面的放置，于是我们可以枚举第一列放地雷方案的放法，然后去掉不符合的，就可以了。根据dp的性质，我们将状态定义为第i列的地雷数。那么我们有：dp[i]=num[i-1]-dp[i-1]-dp[i-2]；（num[i]：=第i列第二行的数目）。那么我们只要判断尾端放置数是不是第二行要求的就可以了，也即：dp[n]+dp[n-1]==num[n]；还有就是我们状态只有:0,1,2的状态，因为一列嘛，那么不符合的剔除。而当我们dp[1]==1时，又明显分为上、下两种，所以乘2。

4.代码：

//D
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#define FAST ios::sync_with_stdio(false)
using namespace std;
const int MAX_N=10000+5;
const int mod = 100000007;
int dp[MAX_N],num[MAX_N];
char s[MAX_N];
int main()
{//freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);long long Case;scanf("%lld",&Case);while(Case--){scanf("%s",s);int len=strlen(s);int res=0;bool flag;for(int i=0;i<len;++i)num[i+1]=s[i]-'0';for(int i=0;i<=num[1];++i){memset(dp,0,sizeof(dp));dp[1]=i;if(i>2) break;flag=1;int ans=1,j;for(j=2;j<=len;++j){dp[j]=num[j-1]-dp[j-1]-dp[j-2];if(dp[j]<0||dp[j]>2){flag=0;break;}if(dp[j]==1) ans=ans*2%mod;}if(dp[1]==1) ans=ans*2%mod;if(j==len+1&&num[len]!=dp[len]+dp[len-1]) flag=0;if(flag) res=(res+ans)%mod;}printf("%d\n",res);}return 0;
}

E - E Kattis - whatdoesthefoxsay

1.题目描述：
Determined to discover the ancient mystery—the sound that the fox makes—you went into the forest, armed with a very good digital audio recorder. The forest is, however, full of animals’ voices, and on your recording, many different sounds can be heard. But you are well prepared for your task: you know exactly all the sounds which other animals make. Therefore the rest of the recording—all the unidentified noises—must have been made by the fox.

Input
The first line of input contains the number of test cases T. The descriptions of the test cases follow:

The first line of each test case contains the recording—words over lower case English alphabet, separated by spaces. Each contains at most 100 letters and there are no more than 100 words. The next few lines are your pre-gathered information about other animals, in the format goes . There are no more than 100 animals, their names are not longer than 100 letters each and are actual names of animals in English. There is no fox goes … among these lines.

The last line of the test case is exactly the question you are supposed to answer: what does the fox say?

Output
For each test case, output one line containing the sounds made by the fox, in the order from the recording. You may assume that the fox was not silent (contrary to popular belief, foxes do not communicate by Morse code).

Sample Input 1
1
toot woof wa ow ow ow pa blub blub pa toot pa blub pa pa ow pow toot
dog goes woof
fish goes blub
elephant goes toot
seal goes ow
what does the fox say?

Sample Output 1
wa pa pa pa pa pa pow

2.题意：
你有个无聊的爱好，录动物的声音，你想知道服哩（狐狸）发出怎么样的声音，你又知道了其他动物怎么叫，那么请筛选出服哩的叫声。

3.思路：
单纯考字符串的模拟题。用map存一下动物的叫声然后开始匹配，剩下的就是服哩的叫声。不过要注意切片的操作。

4.代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#define FAST ios::sync_with_stdio(false)
using namespace std;
int main()
{//freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);long long Case;scanf("%lld",&Case);cin.get();while(Case--){string s1,s[105],tmp,tmp1,tmp2;map<string,string> m;getline(cin,s1);int i,j=0,t=0;for(i=0;i<(int)s1.size();++i){if(s1[i]==' '){tmp=s1.substr(j,i-j);j=i+1;s[t++]=tmp;}}s[t++]=s1.substr(j,i-j);while(true){getline(cin,tmp1);bool flag1=0,flag2=0;j=0;for(i=0;i<(int)tmp1.size();++i){if(tmp1[i]==' '){tmp=tmp1.substr(j,i-j);if(tmp=="what") {flag1=1;break;}else if(tmp=="goes")flag2=true;elsetmp2=tmp;j=i+1;}}if(flag1)break;if(flag2){tmp=tmp1.substr(j,i-j);m[tmp]=tmp2;}}for(int i=0;i<t;++i){if(!m.count(s[i]))cout<<s[i]<<" ";}cout<<endl;}return 0;
}

F - F CodeForces - 545D

1.题目描述：
Little girl Susie went shopping with her mom and she wondered how to improve service quality.

There are n people in the queue. For each person we know time ti needed to serve him. A person will be disappointed if the time he waits is more than the time needed to serve him. The time a person waits is the total time when all the people who stand in the queue in front of him are served. Susie thought that if we swap some people in the queue, then we can decrease the number of people who are disappointed.

Help Susie find out what is the maximum number of not disappointed people can be achieved by swapping people in the queue.

Input
The first line contains integer n (1 ≤ n ≤ 105).
The next line contains n integers ti (1 ≤ ti ≤ 109), separated by spaces.

Output
Print a single number — the maximum number of not disappointed people in the queue.

Examples
Input
5
15 2 1 5 3

Output
4

Note
Value 4 is achieved at such an arrangement, for example: 1, 2, 3, 5, 15. Thus, you can make everything feel not disappointed except for the person with time 5.

2.题意：
人们总是对自己时间非常珍惜，所以呢，人们不希望自己被服务的时间（ghs？？）少于等候的时间，否则人们就会失望滴。有一个小女孩排队的时候想着，如果调换那些人的顺序，会不会少人失望呢？求最少失望滴人数。

3.思路：
一开始我想的是贪心，后来发现，这个贪心还得优化一下，用优先队列，由于前面时间无论你服务完没有都计入时间，那么那些因为前面的人多而得不到服务的理应不管。当时间超过最长服务时间的时候，后面的连同前面不用管的都不管啦。

4.代码：

//F
#include<iostream>
#include<algorithm>
#include<queue>
#define FAST ios::sync_with_stdio(false)
using namespace std;
int main()
{int n,tmp;long long sum=0,ans=0;priority_queue<long long,vector<long long>,greater<long long> > que;cin>>n;for(int i=0;i<n;++i){cin>>tmp;que.push(tmp);}for(int i=0;i<n;++i){tmp=que.top();que.pop();if(sum<=tmp){sum+=tmp;ans++;}}cout<<ans<<endl;return 0;
}

G - G HDU - 5877

1.题目描述：
You are given a rooted tree of N nodes, labeled from 1 to N. To the ith node a non-negative value ai is assigned.An ordered pair of nodes (u,v) is said to be weak if
(1) u is an ancestor of v (Note: In this problem a node u is not considered an ancestor of itself);
(2) au×av≤k.

Can you find the number of weak pairs in the tree?

Input
There are multiple cases in the data set.
The first line of input contains an integer T denoting number of test cases.
For each case, the first line contains two space-separated integers, N and k, respectively.
The second line contains N space-separated integers, denoting a1 to aN.
Each of the subsequent lines contains two space-separated integers defining an edge connecting nodes u and v , where node u is the parent of node v.

Constrains:

1≤N≤105

0≤ai≤109

0≤k≤1018

Output
For each test case, print a single integer on a single line denoting the number of weak pairs in the tree.

Sample Input
1
2 3
1 2
1 2

Sample Output
1

2.题意：

3.思路：

4.代码：

H - H HDU - 6187

1.题目描述：
Long times ago, there are beautiful historic walls in the city. These walls divide the city into many parts of area.
Since it was not convenient, the new king wants to destroy some of these walls, so he can arrive anywhere from his castle. We assume that his castle locates at (0.6∗2–√,0.6∗3–√).
There are n towers in the city, which numbered from 1 to n. The ith’s location is (xi,yi). Also, there are m walls connecting the towers. Specifically, the ith wall connects the tower ui and the tower vi(including the endpoint). The cost of destroying the ith wall is wi.
Now the king asks you to help him to divide the city. Firstly, the king wants to destroy as less walls as possible, and in addition, he wants to make the cost least.
The walls only intersect at the endpoint. It is guaranteed that no walls connects the same tower and no 2 walls connects the same pair of towers. Thait is to say, the given graph formed by the walls and towers doesn’t contain any multiple edges or self-loops.
Initially, you should tell the king how many walls he should destroy at least to achieve his goal, and the minimal cost under this condition.

Input
There are several test cases.
For each test case:
The first line contains 2 integer n, m.
Then next n lines describe the coordinates of the points.
Each line contains 2 integers xi,yi.
Then m lines follow, the ith line contains 3 integers ui,vi,wi
|xi|,|yi|≤105
3≤n≤100000,1≤m≤200000
1≤ui,vi≤n,ui≠vi,0≤wi≤10000

Output
For each test case outout one line with 2 integers sperate by a space, indicate how many walls the king should destroy at least to achieve his goal, and the minimal cost under this condition.

Sample Input
4 4
-1 -1
-1 1
1 1
1 -1
1 2 1
2 3 2
3 4 1
4 1 2

Sample Output
1 1

2.题意：
一个国王为了防止藩镇割据（误），咳咳，是周游诸城，就想把古老的墙拆了，众所周知，拆迁，是要给钱的。问最少要拆多少墙以及花多少钱呢？

3.思路：
本来想着直接套负号然后prim算法的，无奈数据量太大了，所以我们选择一个更为节省的方法——贪心+并查集。先选出n-1条最长的边，把他们用并查集连在一起就好啦！那个这么恐怖的坐标，你看像不像骗你的？

4.代码：

//H
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX_N=100000+5;
int p[MAX_N];
struct node
{int u,v,w;
} wall[MAX_N*2];
bool cmp(node &a,node &b){return a.w>b.w;}
int f(int x){return p[x]==x?x:p[x]=f(p[x]);}
int main()
{int n,m,x,y;//freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);while(~scanf("%d%d",&n,&m)){int sum=0,num=0;for(int i=1;i<=n;++i){cin>>x>>y;p[i]=i;}for(int i=0;i<m;++i){cin>>wall[i].u>>wall[i].v>>wall[i].w;sum+=wall[i].w;}sort(wall,wall+m,cmp);for(int i=0;i<m;++i){int x1=f(wall[i].u),y1=f(wall[i].v);if(x1!=y1){p[x1]=y1;sum-=wall[i].w;num++;if(num==n-1) break;}}cout<<m-num<<" "<<sum<<endl;}return 0;
}

//我会补完的QAQ