浙江大学acm题库答案
① 浙大acm题库1002求助
是FireNet那个题么?
典型的DFS
这个是我的代码:
#include <iostream>
using namespace std;
bool canput(char map[5][5], int y, int x){
if(map[y][x] != '.')return 0;
int i;
for(i = y - 1; i >= 0; i--){
if(map[i][x] == 'X')break;
if(map[i][x] == 'F')return 0;
}
for(i = x - 1; i >= 0; i--){
if(map[y][i] == 'X')break;
if(map[y][i] == 'F')return 0;
}
return 1;
}
void dfs(char map[5][5], int n, int depth, int put, int &max){
if(put > max)max = put;
if(depth >= n*n)
return;
dfs(map,n,depth+1,put,max);
int y = depth / n, x = depth % n;
if(canput(map,y,x)){
map[y][x] = 'F';
put++;
dfs(map, n, depth+1, put, max);
map[y][x] = '.';
put--;
}
}
int main(){
//freopen("input.txt","r",stdin);
char map[5][5];
int i,n,firenet;
while(scanf("%d",&n)!=EOF && n){
firenet = 0;
for(i = 0; i < n; i++)scanf("%s",&map[i]);
dfs(map,n,0,0,firenet);
printf("%d\n",firenet);
}
return 0;
}
② A+B for Input-Output Practice 这是ACM杭大题库的一道题各位大哥大姐们谁知道答案啊
题目的翻译是：
题目 计算a+b
输入：首先输入一个N代表下面的行数，然后在下面每行中输入两个数ai和bi，用空格分开。
输出：输出N行，每行输出ai+bi的和。
算法（不知道你会什么语言，所以只拿自然语言描述了）：
Step1. 获取N，进行标准化判断（即若N不是正整数，则提示错误）；
Step2. 建立数组A[N]；
Step3. For i=1 to N do
{
读入a，b；（更细致一些的话可以加入空格判断，即判断a后第一个不是空格的字符）
将a+b写入A[i]；
}
Step4. For i=1 to N do
{
输出A[i]；
输出回车键；
}
③ 浙江大学 ACM 1047和1119题谁有答案
都用c++交，ac代码如下
1119
#include<stdio.h>
#include<memory.h>
const int Node = 1000;
int n;
bool G[Node][Node];
int father[Node];
int order[Node];
int low[Node];
bool visited[Node];
void DFS(int v, int d)
{
if (visited[v]) return;
low[v] = d;
order[v] = d;
visited[v] = true;
for (int i = 0; i < n; i++) {
if (G[v][i]) {
if (visited[i])
low[v] = low[v]<order[i]?low[v]:order[i];
else {
father[i] = v;
DFS(i, d+1);
low[v] = low[v]<low[i]?low[v]:low[i];
}
}
}
}
void SPF()
{
for (int i = 0; i < n; i++)
{
visited[i] = false;
father[i] = -1;
low[i] = 0;
order[i] = 0;
}
for (int i = 0; i < n; i++)
if (!visited[i]) DFS(i, 1);
bool find = false;
for (int i = 0; i < n; i++)
{
int subnet = 0;
for (int j = 0; j < n; j++)
if ((father[j] == i) && (low[j] >= order[i]))
subnet++;
if (subnet > 0) {
if (father[i] == -1) {
if (subnet > 1) {
find = true;
printf(" SPF node %d leaves %d subnets\n", i+1, subnet);
}
}
else {
find = true;
printf(" SPF node %d leaves %d subnets\n", i+1, subnet+1);
}
}
}
if (!find) {
printf(" No SPF nodes\n");
}
}
int main(){
int i,j;
int number = 0;
memset(G, 0, sizeof(G));
while(scanf("%d", &i)) {
if(i==0) {
if(number) putchar('\n');
printf ("Network #%d\n", ++number);
SPF();
scanf("%d", &i);
if (i==0) break;
memset(G, 0, sizeof(G));
}
n = -1;
scanf("%d", &j);
if(i>n) n = i;
if(j>n) n = j;
G[i-1][j-1] = G[j-1][i-1]=1;
}
}
1047
#include <iostream>
using namespace std;
int a[22][22];
int movex[8]={-1,-1,-1,0,1,1,1,0};
int movey[8]={-1,0,1,1,1,0,-1,-1};
void sel(int x,int y){
a[x][y]=2;
int i,tempi,tempj;
for(i=0;i<8;i++){
tempi=x+movex[i];
tempj=y+movey[i];
if(a[tempi][tempj]==1) sel(tempi,tempj);
}
}
int main(void){
int i,j;
int row,col,x,y,c;
while(cin>>row>>col>>x>>y&&!(row==0&&col==0&&x==0&&y==0)){
char* temp=new char[col+1];
for(i=1;i<=row;i++){
cin>>temp;
for(j=1;j<=col;j++){
if(temp[j-1]=='.') a[i][j]=0;
else a[i][j]=1;
}
}
delete []temp;
for(i=0;i<=col+1;i++) a[0][i]=a[row+1][i]=0;
for(i=0;i<=row+1;i++) a[i][0]=a[i][col+1]=0;
sel(x,y);
c=0;
for(i=1;i<=row;i++){
for(j=1;j<=col;j++){
if(a[i][j]!=2) continue;
if(a[i-1][j]==0) c++;
if(a[i+1][j]==0) c++;
if(a[i][j-1]==0) c++;
if(a[i][j+1]==0) c++;
}
}
cout<<c<<endl;
}
return 0;
}
④ 求浙江大学acm题目 2918 和2920 的代码...
#include <stdio.h>
#include <string.h>
#define N 110
#define eps 1e-8
char map[N][N];
double visit[N][N]; //到该点的概率
double deal ( int c, int n, int m ) {
int i, j;
double ans = 0;
memset ( visit, 0, sizeof ( visit ) );
visit[ 0 ][ c ] = 1;
for ( i = 0 ; i < n - 1 ; ++i ) { //这里我用的是向下扩展
for ( j = 0 ; j < m ; ++j ) {
if ( visit[ i ][ j ] > eps ) {
if ( map[ i ][ j ] != '.' ) { //有概率就一定不是'*' 并且又不是'.'的情况下就是数字了
ans += visit[ i ][ j ] * ( map[ i ][ j ] - '0' );
}
else {
if ( map[ i + 1 ][ j ] != '*' ) { //不是'*'的地方直接继承
visit[ i + 1 ][ j ] += visit[ i ][ j ];
}
else {
if ( j > 0 ) { //向左下右下扩展
visit[ i + 1 ][ j - 1 ] += visit[ i ][ j ] / 2;
}
if ( j < m - 1 ) {
visit[ i + 1 ][ j + 1 ] += visit[ i ][ j ] / 2;
}
}
}
}
}
}
for ( i = 0 ; i < m ; ++i ) { //最后一行特别处理下
if ( map[ n - 1 ][ i ] != '*' && map[ n - 1 ][ i ] != '.' ) {
ans += visit[ n - 1 ][ i ] * ( map[ n - 1 ][ i ] - '0' );
}
}
return ans;
}
int main () {
int i, n, m, t;
double ans, temp;
scanf ( "%d", &t );
while ( t-- ) {
scanf ( "%d%d", &n, &m );
getchar();
for ( i = 0 ; i < n ; ++i ) {
gets( map[ i ] );
if ( map[ i ][ 0 ] == '\0' ) --i;
}
ans = 0;
for ( i = 0 ; i < m ; ++i ) {
if ( map[ 0 ][ i ] != '.' ) { //特判下第一行
if ( map[ 0 ][ i ] == '*' ) temp = 0;
else temp = map[ 0 ][ i ] - '0';
}
else temp = deal( i, n, m ); //向下搜索
if ( temp - ans > eps ) ans = temp;
}
printf ( "%.6lf\n", ans );
}
return 0;
}
这个题主要是不能用队列直接去搜索 如果那样队列不够用的 因为100 行 如果50个'*' 按金字塔排就有2^50次了
注释是c++形式的 交上去会CE哈 去掉了可以过
唉 要上课去了 2920 等晚上再说了
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#define N 60
#define M 15
using namespace std;
struct line {
int solve[ M ];// 判断问题是否已被解决
int re_times[ M ];// 问题解决之前错误的次数
vector< pair< int, int > > record; // 记录分数变动的情况 pair前者为变动时间 后者为该变动之前的罚时
int ans, time; // ans 为解决题数 time 为总用时
} f[ N ];
const string AC = "accepted";
map< string, int > data;
vector< string > rank;
int judge[ N ][ N ];
void init () {
for ( int i = 0 ; i < N ; ++i ) {
memset ( f[ i ].solve, 0, sizeof ( int ) * M );
memset ( f[ i ].re_times, 0, sizeof ( int ) * M );
f[ i ].record.clear();
f[ i ].ans = f[ i ].time = 0;
}
memset ( judge, 0, sizeof( judge ) );
data.clear();
rank.clear();
return;
}
bool cmp ( const string& a, const string& b ) {
struct line *temp1 = &f[ data[ a ] ], *temp2 = &f[ data[ b ] ];
if ( temp1->ans != temp2->ans ) return temp1->ans > temp2->ans;
if ( temp1->time != temp2->time ) return temp1->time < temp2->time;
int i;
for ( i = temp1->record.size() - 1 ; i >= 0 ; --i ) {
if ( temp1->record[ i ].first != temp2->record[ i ].first ||
temp1->record[ i ].second != temp2->record[ i ].second ) break;
}
if ( i < 0 ) {
judge[ data[ a ] ][ data[ b ] ] = judge[ data[ b ] ][ data[ a ] ] = 1;// 如果完全一样的话 就标记下
return a < b;
}
else {
if ( temp1->record[ i ].first != temp2->record[ i ].first ) return temp1->record[ i ].first < temp2->record[ i ].first;
else return temp1->record[ i ].second < temp2->record[ i ].second; // 这里注意 过的题数一定是相同的 否则又先后到话 时间就不同了
}
}
bool cmp0 ( const pair< int, int >& a, const pair< int, int >& b ) {
return a.first < b.first;
}
int main () {
int i, j, k, t, n, m, time;
string str, name, result;
struct line* now;
char problem;
cin >> t;
while ( t-- ) {
init ();
cin >> n >> m;
for ( i = 0 ; i < n ; ++i ) {
cin >> str;
data[ str ] = i;
rank.push_back ( str );
}
for ( i = 0 ; i < m ; ++i ) {
cin >> time >> name >> problem >> result;
now = &f[ data[ name ] ];
if ( now->solve[ problem - 'A' ] ) continue;
if ( result == AC ) {
now->solve[ problem - 'A' ] = 1;
pair< int, int > temp;
temp.first = time;
temp.second = now->time; // 注意是该时间点之前的罚时 所以要先记录 后+当前罚时
now->time += time + now->re_times[ problem - 'A' ] * 20;
++now->ans;
now->record.push_back( temp );
}
else {
++now->re_times[ problem - 'A' ];
}
}
for ( i = 0 ; i < n ; ++i ) {
sort ( f[ i ].record.begin(), f[ i ].record.end(), cmp0 );// 按发生时间排序
}
sort ( rank.begin(), rank.end(), cmp );
for ( k = 0 ; k < n ; ++k ) { // 这里对前面的标记进行处理 使每两组数据的关系都确定了 (有点暴力的.....)
for ( i = 0 ; i < n ; ++i ) {
for ( j = 0 ; j < n ; ++j ) {
if ( judge[ i ][ k ] && judge[ k ][ j ] ) {
judge[ i ][ j ] = 1;
}
}
}
}
for ( i = j = 0 ; i < rank.size() ; ++i ) {
now = &f[ data[ rank[ i ] ] ];
if ( i && judge[ data[ rank[ i ] ] ][ data[ rank[ j ] ] ] == 0 ) j = i;
cout<< j + 1 << ' '
<< rank[ i ] << ' '
<< now->ans << ' '
<< now->time << endl;
}
}
return 0;
}
好了 终于过了 惭愧啊 题没看清 WA了很多次
有什么不清楚留言吧....
⑤ 浙大acm题高手进 http://acm.zju.e.cn/onlinejudge/showProblem.doproblemCode=3208
看你的代码看的蛋疼。 先说说你的思路吧。
我觉得应该仿照图的常用算法，也就是贪心算法。
核心数据结构为
struct Distance
{
double val; // distance value
int adj_tree; // index of the adjacent tree to which we calculate the distance
};
struct Tree
{
double x, y; // coordinates
Distance* dist_array; // distance to each tree
double dist_to_observer; // distance to the observer
bool grown; // the tree has grown up
};
思路为：
1. 对每棵树保留其到其他所有树的距离并排序（这样dist_array[0]肯定是自己,无视之）
2. 选出有全场最小距离的树(要么dist_array[1]全场最小，要么dist_to_observer全场最小)
3. 计算出此树的最大半径：
a. radius = dist_to_observer
b.遍历dist_array，若adj_tree已经grow则radius取现值和val的较小值，若未grow则取现值和val/2的较小值
c.如果这颗树的radius史上最大则保存
4. 令其长大，set grown=true。
5. 对任一其它树的dist_array中和当前树相关的距离减去radius
6. 遍历当前树的dist_array，找到第一个尚未grow的树，设定为当前树，跳到3，若找不到则结束
在步骤3或者4中求出过observer到当前树形成的园的两根切线形成的角度区间，
保存下来，不断并集，最后如果能够撑满(0, 2*PI),则最大radius为所求，否则-1。
我不是什么acm高手，所以以上算法效率也不是很高，如果你有更好的算法也请提出来一起来研究研究。
⑥ 浙江大学的ACM题目求解，只需答对其中一道
很老的题目了 ，占位
⑦ http://acm.zju.e.cn/onlinejudge/showProblem.doproblemId=5274 浙大acm的这道题
排序效率太低
逻辑错误1处，当某个学生用了卡以后，不应该用k=k+b，而是k应该那个学生进入的时间+b
#define_CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
typedefstruct{
inttime;
intindex;
}student;
intsortByTime(constvoid*a,constvoid*b){
return((student*)a)->time-((student*)b)->time;
}
intsortByAcs(constvoid*a,constvoid*b){
return*((int*)a)-*((int*)b);
}
intmain()
{
intt,a,b,c,d,e,h,i,j,k;
studentf[20005];
intg[200005];
scanf("%d",&t);
while(t--)
{
h=0;
scanf("%d%d",&a,&b);
for(i=1;i<=a;i++)
{
scanf("%d:%d:%d",&c,&d,&e);
f[i].time=(c*3600)+(d*60)+e;
f[i].index=i;
}
qsort(f+1,a,sizeof(student),sortByTime);
k=f[1].time;
for(i=1;i<=a;i++)
if(k<=f[i].time)
{
g[h]=f[i].index;
h=h+1;
k=f[i].time+b;
}
qsort(g,h,sizeof(int),sortByAcs);
printf("%d %d",h,g[0]);
for(i=1;i<h;i++)
printf("%d",g[i]);
printf(" ");
}
return0;
}
⑧ http://acm.zju.e.cn/onlinejudge/showProblem.doproblemCode=2110 #include<iostream> #include<cmat
1. map[9][9]这样的一个定义从哪里得到的？ 或许你是想做一个9*9的空间，然后根据原题1 < N, M < 7的限制，把迷宫放在其中。如果只是放迷宫的话，那么6*6的空间已经足够
如果为了减少干扰 想在迷宫外面人为加上一圈墙的话，那么8*8就可以了，当然，9*9也行 只是大了一圈
可是在你的输入模块中，还是从0开始输入，也没有看到加墙的代码
在检查函数dfs中做map[si+dir[i][0]][sj+dir[i][1]]!='X'这样的操作时 就可能会出现map[-1][x]类似的越界情况
2.可能是笔误吧 在输入模块中，读入字符存在char temp中，可是我只看到了一系列对map[][]的判断，却没有把temp写入map中语句
for(i=0;i<n;i++) {
for(j=0;j<m;j++)
{
scanf("%c",&temp);
map[i][j] = c;
...
先把这些改了 你再试试吧
⑨ 浙江大学ACM题库是什么
ACM是美国计算机协会，那题库里都是编程有关的题目，计算机专业的人比较了解，现在大学里应该都有这个ACM协会在发展成员，主要是计算机专业的学生，学得好的人回去参加省赛，全国邀请赛，亚洲赛甚至世界赛等等，那题库里的题都是给他们用来练习的，而且大部分都是英文题，因为从省赛开始题目就全是英文题了，呵呵