2015安徽省青少年信息学奥林匹克(AHOI)初中组
2015AHOI初中-T1- 猜谜游戏 [unique]
题目描述
滨湖幼儿园的老师带着N位小朋友在玩游戏。
他们玩的是猜谜游戏，在每一轮游戏中，每一位小朋友都需要给出一个在1到100之间的整数（包括1和100）。对于每一位小朋友来说，如果他给出来的数字式唯一的，或者说没有别的小朋友给出来相同的数字，则他就可以获得与所选数字相同的得分，否则得零分。
现在他们一共进行了三轮游戏。老师希望知道三轮游戏之后，每一位小朋友分别可以得到多少分数。
输入格式
输入有1+N行。
其中第一行给出一个正整数N(2≤N2≤200）表示参与游戏的小朋友有多少位。
之后N行中的第i行（1≤i≤N）给出三个大于等于1小于等于100的正整数。
分别表示第i位小朋友三轮游戏中分别给出的数字是多少。
输出格式
输出有N行。其中第i行（1≤i≤N）给出了第i个小朋友在经过了三轮游戏之后，可以合计得到的分数。
输入输出样例
输入样例1：
输出样例1：
输入样例2：
输出样例2：
说明
数据规模：
对于40%的数据，满足N <= 50
对于100%数据，满足N <= 200"
提示说明
对于样例一来说，假设五位小朋友分别名为Anold，Borel，Cayler，David和Einstein，则每一个人三轮游戏之后的得分情况如下所示：
Anold : 0 + 0 + 0 = 0
Borel : 0 + 0 + 92 = 92
Cayler : 63 + 89 + 63 = 215
David : 99 + 0 + 99 = 198
Einstein : 89 + 0 + 0 = 89
耗时限制1000ms 内存限制64MB
解析
考点：数组标记
参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e2+5;
int n, a[N][3], f[N], s[N];
int main(){
cin >> n;
for(int i = 1; i <= n; i++) {
for(int j = 0; j < 3; j++) {
cin >> a[i][j];
}
}
for(int j = 0; j < 3; j++) {
memset(f, 0, sizeof f);
for(int i = 1; i <= n; i++) {
f[a[i][j]]++;
}
for(int i = 1; i <= n; i++) {
if(f[a[i][j]] == 1)
s[i] += a[i][j];
}
}
for(int i = 1; i <= n; i++)
cout << s[i] << '\n';
return 0;
}
2015AHOI初中-T2- 小岛 [islet] P2683
题目描述
西伯利亚北部的寒地，坐落着由N个小岛组成的岛屿群，我们把这些小岛依次编号为1到N。
起初，岛屿之间没有人和航线，后来随着交通的发展，逐渐出现了一些联通两座小岛的航线。例如增加一条在u号小岛与v号小岛之间的航线，这条航线的用时为e。那么沿着这条航线，u号小岛上的人可以前往v号小岛，同样的v号小岛上的人也可以前往u号小岛，其中沿着这一条航线花费的时间为e。
同时，随着旅游业的发展，越来越多的人前来游玩。那么两个小岛之间的最短路径是多少便成为了饱受关注的话题。
输入格式
输入文件islt.in共M+1行。
第一行有两个整数N和M,分别表示小岛的数和总操作数。
接下来的M行，每行表示一个操作，格式如下：
0 s t：表示询问从s号小岛到t号小岛的最短用时（1≤s≤n，1≤t≤n，s≠t）。
1 u v e：表示新增了一条从u号小岛到v号小岛，用时为e的双向航线（1≤u≤n，1≤v≤n，u≠v，1≤e≤10^5）
输出格式
输出文件islet.out针对每一次询问，单独输出一行。对于每一组询问来说，如果不存在可行的道路，则输出-1，否则输出最短用时。
输入输出样例
输入样例1：
输出样例1：
输入样例2：
输出样例2：
说明
数据规模
对于20%的数据，N ≤ 5且M ≤ 30。
对于40%的数据，N ≤ 20且M ≤ 200。
对于60%的数据，N ≤ 80且M ≤ 500。
对于80%的数据，N ≤ 100且M ≤ 2500。
对于100%的数据，N ≤ 100且M ≤ 5000。
耗时限制1000ms 内存限制64MB
解析
考点：图论，最短路，最小生成树
思路：
本题正解Floyed，考虑一次修改边的操作，将受到这条边影响的点枚举出来。（这条边相当于枚举中的K）。 有以下修改最短路的方式：
f[i][j]=f[i][s]+f[s][t]+f[t][j]
其中 f[s][t]表示刚刚读入的进行修改的边
对每次读入最新修改的边枚举 i,j更新最短路这样做 m 次就完了。
时间复杂度O((n^2)*m)
参考代码
#include<cstdio>
const int inf=199999990;
int n,m,f[101][101];
int main(){
int a,s,t,e;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i!=j)f[i][j]=inf;
}
}
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a,&s,&t);
if(a==0){
if(f[s][t]!=inf)printf("%d\n",f[s][t]);
else printf("-1\n");
}
else{
scanf("%d",&e);
if(e<f[t][s]){
f[t][s]=f[s][t]=e;
for(int k=1;k<=n;k++){
for(int l=1;l<=n;l++){
if(f[k][s]+f[s][t]+f[t][l]<f[k][l])
f[k][l]=f[l][k]=f[k][s]+f[s][t]+f[t][l];//核心语句更新f[k][l]的最短路
}
}
}
}
}
return 0;
}
2015AHOI初中-T3- 上学路上 [school]
题目描述
小雪与小可可吵架了，他们决定以后互相再也不理对方了。尤其是，他们希望以后上学的路上不会再相遇。
我们将他们所在城市的道路网视作无限大的正交网络格，每一个整点数（x，y）对应了一个路口，相邻两个整数点之间有一条平行于x轴或平行于y轴的道路，其道路长度为1.已经知道小雪家住在（x1,0）处的路口附近，小可可的家住在（x2,0）处的路口附近。另外我们还知道，小学的学校在（0，y1）处的路口附近，小可可的学校在（0，y2）处的路口附近。其中保证x1＜x2，且y1＜y2。
因为上学不能迟到，所以小雪和小可可总是希望可以走最短路径去上学。同时为了避免见面，希望他们所选择的路线可以没有交点。
输入格式
输入文件的第一行输入四个正整数，依次为x1，x2，y1，y2，满足x1＜x2，且y1＜y2。
输出格式
在输出文件中，输出一个非负整数，表示可行方案的总数ans关于常数10^9+7取余后的值。
输入输出样例
输入样例1：
输出样例1：
输入样例2：
输出样例2：
输入样例3：
输出样例3：
说明
数据规模：
对于30%的数据，0＜x1，x2，y1，y2≤500。
对于70%的数据，0＜x1，x2，y1，y2≤3000。
对于100%的数据，0＜x1，x2，y1，y2≤100000。
提示说明：
对于样例一来说，一共有三种可行方案，如下图所示。
耗时限制1000ms 内存限制64MB
解析：
考点：组合数学，容斥原理，计数原理
本题考虑用容斥的思想。先求出没有限制的总方案数，然后求出有路径相交的方案数，再相减即可。
参考代码：
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#define ll long long
#define mod 1000000007
using namespace std;
int x1,x2,y1,y2,fac[200005];
void pre(){
fac[1]=1;
for(int i=2;i<=y2+x2+10;i++)
fac[i]=1ll*fac[i-1]*i%mod;
}
int mul(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*ans*a%mod;
a=1ll*a*a%mod;b>>=1;
}
return ans;
}
int calc(int x,int y){
int ans=1ll*fac[x+y]*mul(fac[x],mod-2)%mod;
ans=1ll*ans*mul(fac[y],mod-2)%mod;
return ans;
}
int main(){
scanf("%d%d%d%d",&x1,&x2,&y1,&y2);pre();
int t1=1ll*calc(x1,y1)*calc(x2,y2)%mod;
int t2=1ll*calc(x1,y2)*calc(x2,y1)%mod;
printf("%d",(t1-t2+mod)%mod);
return 0;
}
2015AHOI初中-T4- 琵琶湖 [lakebiwa]
题目描述
滋贺县的琵琶湖享有盛名，尤其是湖中央的琵琶岛。
琵琶岛不仅是外观上是矩形的，而且还被分割为了nxm的格子图。每一块格子区域都有着确定的高度。不幸的是，琵琶湖的水位最近开始上涨了，第i年湖面的高度将上涨至i米。另外一方面，琵琶岛是有松软的土质形成的，且琵琶湖的湖水可以自由渗入到其中。也就是说，如果有一块格子区域的高度不超过当前的水位，则将被淹没。相连的未被淹没的个字（有这公共边的格子区域）将组成一块未被淹没的区域。
现在，小可可希望知道对于制定某一年来说，琵琶岛被分割为了多少块未被淹没的区域。
输入格式
输入文件的第一行有两个整数n和m，由一个空格隔开，表示琵琶岛的大小。
之后n行，每行有m个正整数，在[1,10^9]范围内，表示了对应格子区域的高度。
之后一行有一个整数T.再之后的一行，有T个整数tj,满足0≤t1≤t2≤...≤tT-1≤tT≤10^9
输出格式
在输出文件中，你的程序应该输出单独一行，包含T个整数rj以空格隔开。其中rj表示了再第tj年，未被淹没的区域的个数。
输入输出样例
输入样例1：
输出样例1：
说明
对于20的数据，1 ≤ n ≤ 100, 1 ≤ m ≤ 100, 1 ≤ T ≤ 2000
有20%的数据，n = 1, 1 ≤ m ≤ 1000, 1 ≤ T ≤ 10 ^5
还有20%的数据，n = 2, 1 ≤ m ≤ 1000, 1 ≤ T ≤ 10^5
对于100%的数据，1 ≤ n ≤ 1000, 1 ≤ m ≤ 1000, 1 ≤ T ≤ 10^5
解析：
考点：并查集
参考代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5, M = 1e3+5;
int n, m, T, t[N], flag[M][M], res[M*M];
int fa[M*M], siz[M*M];
struct P{
int x, y, h;
bool operator<(const P& rhs) const {
return h > rhs.h;
}
} a[M*M];
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
int find(int x) {
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void merge(int x, int y) {
x = find(x);
y = find(y);
if(siz[x] < siz[y]) swap(x, y);
fa[y] = x;
siz[x] += siz[y];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
int tmp;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> tmp;
int t = (i-1)*m+j;
a[t] = {i,j,tmp};
fa[t] = t;
siz[t] = 1;
}
}
sort(a+1, a+n*m+1);
cin >> T;
for(int i = 1; i <= T; i++) cin >> t[i];
int now = 1, ans = 0;
for(int i = T; i >= 1; i--) { // 倒序枚举
while(now <= n*m &&a[now].h > t[i]) {
ans++;
int cx = a[now].x, cy = a[now].y;
flag[cx][cy] = 1;
for(int j = 0; j < 4; j++) {
int nx = cx + dx[j], ny = cy+dy[j];
if(nx<1||nx>n||ny<1||ny>m||!flag[nx][ny])
continue;
int p1 = (nx-1)*m+ny, p2 = (cx-1)*m+cy;
if(find(p1)!=find(p2)) { // 两个区域相邻，可以合并
merge(p1, p2);
ans--;
}
}
now++;
}
res[i] = ans;
}
for(int i = 1; i <= T; i++)
cout << res[i] << ' ';
return 0;
}