浙江大學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協會在發展成員，主要是計算機專業的學生，學得好的人回去參加省賽，全國邀請賽，亞洲賽甚至世界賽等等，那題庫里的題都是給他們用來練習的，而且大部分都是英文題，因為從省賽開始題目就全是英文題了，呵呵