読者です 読者をやめる 読者になる 読者になる

夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

PKUって平和だよね・・・

2385

記憶喪失

#include <cstdio>
int main() {
	int T, W;
	scanf("%d%d", &T, &W);
	int tree[T];
	for (int i=0; i<T; i++) scanf("%d", &tree[i]);
	int res = 0;
	for (int i=0; i<T; i++) {
		int chn = 0;
		int cnt = 1;
		int tmp = tree[i];
		for (int j=i+1; j<T && chn <= W; j++) {
			if (tmp != tree[j]) {
				chn++;
				tmp = tree[j];
				if (chn == W+1) break;
			}
			cnt++;
		}
		if (res < cnt) res = cnt;
	}
	printf("%d\n", res);
}

2389

多倍長ゲー、Javaゲー

import java.math.*;
import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner std = new Scanner(System.in);
		BigInteger R, S;
		R = std.nextBigInteger();
		S = std.nextBigInteger();
		System.out.println(R.multiply(S));
	}
}

2387

ダイクストラ、実装がんばった

#include <cstdio>
#include <vector>
#include <climits>
#include <queue>
#include <functional>
using namespace std;
struct edge { 
	int to, cost;
	edge(int _to, int _cost) { to = _to; cost = _cost; }
};
typedef pair<int, int> P;
int main() {
	int T, N;
	scanf("%d%d",&T,&N);
	vector<edge> G[N];
	int d[N];
	for (int i=0; i<T; i++) {
		int x, y, cost;
		scanf("%d%d%d", &x,&y,&cost);
		G[x-1].push_back(edge(y-1,cost));
		G[y-1].push_back(edge(x-1,cost));	
	}
	priority_queue<P, vector<P>, greater<P> > que;
	fill(d, d+N, INT_MAX);
	d[N-1] = 0;
	que.push(P(0,N-1));
	while (!que.empty()) {
		P p = que.top(); que.pop();
		int v = p.second;
		if (d[v] < p.first) continue;
		for (int i=0; i<G[v].size(); i++) {
			edge e = G[v][i];
			if (d[e.to] > d[v] + e.cost) {
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
	printf("%d\n", d[0]);
}

2312

関数名dfsだけどタダのBFSですw

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<string> vs;
typedef pair<int, int> P;
const int MA = 100000;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,-1,1};
int sy, sx, gy, gx;
vs map;
vii d;
int dfs() {
	queue<P> que;
	que.push(P(sy, sx));
	int N=map[0].length(), M=map.size();
	for (int i=0; i<M; i++) for (int j=0; j<N; j++) d[i][j]=MA;
	d[sy][sx] = 0;
	while (que.size()) {
		P p = que.front();
		que.pop();
		if (p.first==gy && p.second==gx) break;
		for (int i=0; i<4; i++) {
			int ny=p.first+dy[i];
			int	nx=p.second+dx[i];
			if (0<=nx&&nx<N&&0<=ny&&ny<M) {
				if ((map[ny][nx]=='E'||map[ny][nx]=='T')&&
						d[ny][nx]>d[p.first][p.second]+1) {
					que.push(P(ny, nx));
					d[ny][nx]=d[p.first][p.second]+1;
				} else if (map[ny][nx]=='B'&&
						d[ny][nx]>d[p.first][p.second]+2) {
					que.push(P(ny, nx));
					d[ny][nx]=d[p.first][p.second]+2;
				}
			}
		}
	}
	return d[gy][gx];
}

int main() {
	int M, N;
	while (cin>>M>>N) {
		if (M==0&&N==0) break;
		map = vs(M);
		for (int i=0; i<M; i++) cin>>map[i];
		int i, j;
		for (i=0; i<M; i++) {
			for (j=0; j<N; j++) { 
				if (map[i][j]=='Y') {
					sx = j;
					sy = i;
				} else if (map[i][j]=='T') {
					gx = j;
					gy = i;
				}
			}
		}
		d = vii(M,vi(N));
		cout << dfs() << endl;
	}
}
広告を非表示にする