宁波校赛解题报告（by 「D.Ten）
//OJ:http://acm.nbut.cn/
//NBUT2012校赛I(東方Project專題) 网络同步赛 (共9题 目前AC8题)
PS: 剩1题
H题(1121)：几何(没学)
//A [1114] Alice's Puppets
//邻接矩阵 125MS
#include<iostream>
#include<string>
#include<queue>
using namespace std;
#define N 2005
#define M 25
int n,cnt;
int map[N][N],visit[N];
queue<int>Q;
struct node{
char name[M];
int num;
}arr[N];
int add(char x[]){
int i;
for(i = 1; i <= cnt; ++i)
if(!strcmp(arr[i].name,x))
return i;
strcpy(arr[++cnt].name,x);
return cnt;
}
int cmp(const void *a,const void *b){
if((*(node *)a).num != (*(node *)b).num)
return (*(node *)a).num - (*(node *)b).num;
return strcmp((*(node *)a).name,(*(node *)b).name);
}
int main(){
int i;
int a,b;
char c1[M],c2[M];
while(scanf("%d",&n)!=EOF){
cnt = 0;
memset(map,0,sizeof(map));
memset(visit,0,sizeof(visit));
for(i = 1; i <= n; ++i){
scanf("%s %s",c1,c2);
a = add(c1);
b = add(c2);
map[b][a] = 1;
}
int s = add("Alice");
Q.push(s);
arr[s].num = 0;
while(!Q.empty()){
int p =Q.front();
Q.pop();
visit[p] = 1;
for(i = 1; i <= cnt; ++i)
if(map[p][i] && !visit[i]){
arr[i].num = arr[p].num + 1;
visit[i] = 1;
Q.push(i);
}
}
qsort(arr+1,cnt,sizeof(arr[0]),cmp);
for(i = 2; i <= cnt; ++i)
printf("%s %d\n",arr[i].name,arr[i].num);
}
return 0;
}
//A [1114] Alice's Puppets
//邻接表 31MS
#include<iostream>
#include<string>
#include<queue>
using namespace std;
#define N 2005
#define M 25
int n,cnt;
int visit[N];
int head[N],num;
queue<int>Q;
struct node{
char name[M];
int num;
}arr[N];
struct Edge{
int from;
int to;
int next;
}edge[N*N];
void addedge(int from, int to){
edge[num].from = from;
edge[num].to = to;
edge[num].next = head[from];
head[from] = num++;
}
int add(char x[]){
int i;
for(i = 1; i <= cnt; ++i)
if(!strcmp(arr[i].name,x))
return i;
strcpy(arr[++cnt].name,x);
return cnt;
}
int cmp(const void *a,const void *b){
if((*(node *)a).num != (*(node *)b).num)
return (*(node *)a).num - (*(node *)b).num;
return strcmp((*(node *)a).name,(*(node *)b).name);
}
int main(){
int i;
int a,b;
int q,u;
char c1[M],c2[M];
while(scanf("%d",&n)!=EOF){
cnt = num =0;
memset(visit,0,sizeof(visit));
memset(head,-1,sizeof(head));
for(i = 1; i <= n; ++i){
scanf("%s %s",c1,c2);
a = add(c1);
b = add(c2);
addedge(b,a);
}
int s = add("Alice");
Q.push(s);
arr[s].num = 0;
while(!Q.empty()){
int p =Q.front();
Q.pop();
visit[p] = 1;
for(q = head[p]; q!=-1; q= edge[q].next){
u = edge[q].to;
if(!visit[u]){
arr[u].num = arr[p].num + 1;
visit[u] = 1;
Q.push(u);
}
}
}
qsort(arr+1,cnt,sizeof(arr[0]),cmp);
for(i = 2; i <= cnt; ++i)
printf("%s %d\n",arr[i].name,arr[i].num);
}
return 0;
}
//B [1115] Cirno's Trick
#include<iostream>
#include<stdlib.h>
using namespace std;
#define N 10
double arr[N];
int cmp( const void *a , const void *b ){
return *(double *)a > *(double *)b ? 1 : -1;
}
int main(){
int i,n;
while(scanf("%d",&n)!=EOF){
for(i = 0; i < n ; ++i )
scanf("%lf",&arr[i]);
qsort(arr,n,sizeof(arr[0]),cmp);
double ans = 0;
for(i = 1 ; i < n-1; ++ i)
ans += arr[i];
printf("%.2lf\n",ans/(n-2));
}
return 0;
}
//C [1116] Flandre's Passageway 【DP 最长上升子序列】
#include<iostream>
#include<cmath>
#include<stdlib.h>
#include <algorithm>
using namespace std;
#define N 2005
int n,m,k;
struct node{
int x;
int y;
}arr[N];
int cmp(node a,node b) {
return a.x < b.x;
}
int dp[N];
int LIS(int n)
{
int i,j;
for(i=1; i<=n; ++i)
dp[i] = 0;
int ans;
dp[1] = 1;
for(i=2; i<=n; ++i)
{
ans = dp[i];
for(j=1; j<i; ++j)
{
if(arr[i].x>arr[j].x && arr[i].y>arr[j].y && dp[j]>ans)
ans = dp[j];
}
dp[i] = ans+1;
}
ans = 0;
for(i=1; i<=n; ++i)
{
if(dp[i] > ans)
ans = dp[i];
}
return ans;
}
int main(){
int i,j;
while(scanf("%d %d %d",&n,&m,&k)!=EOF){
for(i =1; i <= k; ++i)
scanf("%d %d",&arr[i].x,&arr[i].y);
sort(arr+1,arr+1+k,cmp);
int max = LIS(k);
double bx = (n+m-2*max)*100+sqrt(2.0)*100*max;
printf("%d\n",(int)(bx+0.5));
}
return 0;
}
/*
4 5
5
1 1
3 2
2 2
5 2
6 3
max = 3
*/
//D [1117] Kotiya's Incantation
/*
check: '-'作为结束符 回车则是下一个数据的第一个
GM的提示：a-a-\na-a- 那么第一组数据是SAME而第二组是SIMILAR，至于为什么，想想回车就知道
啦
*/
#include<iostream>
using namespace std;
#define Min(a,b) ((a<b)?(a):(b))
#define Max(a,b) ((a>b)?(a):(b))
#define N 10000
char a[N],b[N];
int cnt1,cnt2;
char c;
int main(){
int i,j;
int flag;
cnt1 = cnt2 = -1;
flag = 0;
while(scanf("%c",&c)!=EOF){
while(c!='-'){
a[++cnt1] = c;
scanf("%c",&c);
}
a[cnt1+1] = '\0';
scanf("%c",&c);
while(c!='-'){
b[++cnt2] = c;
scanf("%c",&c);
}
b[cnt2+1] = '\0';
if(!strcmp(a,b))
printf("SAME\n");
else{
for(i = 0,j = -1; i <= cnt1; ++i)
if(('a' <= a[i] && a[i] <= 'z')||('A' <= a[i] && a[i] <=
'Z'))
a[++j] = a[i];
cnt1 = j;
a[cnt1+1] = '\0';
for(i = 0 ,j = -1; i <= cnt2 ; ++i)
if(('a' <= b[i] && b[i] <= 'z')||('A' <= b[i] && b[i] <=
'Z'))
b[++j] = b[i];
cnt2 = j;
b[cnt2+1] = '\0';
if(!strcmp(a,b))
printf("SIMILAR\n");
else
printf("DIFFERENT\n");
}
c = getchar();
cnt1 = cnt2 = -1;
if(c == -1)
flag = 1;
else {
if(c!='-')
a[++cnt1] = c;
}
if(flag)
break;
}
return 0;
}
//E [1118] Marisa's Affair
#include<iostream>
#include<string>
#include <algorithm>
#include<stdlib.h>
using namespace std;
#define N 5005
#define M 25
struct node{
char name[M];
int num;
int x;
}arr[N];
int n,cnt;
void add(char x[],int y){
int i;
for(i = 0; i <= cnt; ++i)
if(!strcmp(arr[i].name,x)){
arr[i].num += y;
arr[i].x++;
break;
}
if(i>cnt){
strcpy(arr[++cnt].name,x);
arr[i].num = y;
arr[i].x = 1;
}
}
int cmp(const void *a, const void *b){
if((*(node *)b).num != (*(node *)a).num)
return (*(node *)b).num - (*(node *)a).num;
if((*(node *)b).x != (*(node *)a).x)
return (*(node *)b).x - (*(node *)a).x;
return strcmp((*(node *)a).name,(*(node *)b).name);
}
int main(){
char temp[M];
int num,i,j;
while(scanf("%d",&n)!=EOF){
cnt = 0;
for(j =1; j <= n; ++j){
scanf("%s %d",temp,&num);
add(temp,num);
}
qsort(arr+1,cnt,sizeof(arr[0]),cmp);
printf("%d\n",cnt);
for(i =1; i <= cnt; ++i)
printf("%s %d %d\n",arr[i].name,arr[i].num,arr[i].x);
}
return 0;
}
//F [1119] Patchouli's Books
/*
解题思路:
全排列 输出时
对每一位加权判重复
越前面的加的权值越大
*/
#include<iostream>
#include<algorithm>
using namespace std;
int v[10],num[10],ran[10];
long long now,temp;
long long pow(long long x,long long y){
int i;
if(y == 0)
return 1;
for(i = 1; i <= y; ++i)
x *= 16;
return x;
}
void DFS(int deep,int n){
int i;
if(deep == n){
int b =0;
temp = 0;
for(i = 0; i < n; ++i)
temp += num[ran[i]]*pow((long long)1,(long long)n-i);
if(temp > now){
now = temp;
for(i = 0 ; i < n; i++) {
if(i < n-1)
printf("%X ",num[ran[i]]);
else
printf("%X\n",num[ran[i]]);
}
}
return ;
}
for(i = 0;i < n;i++){
if(v[i]==0){
ran[deep] = i;
v[i] = 1;
DFS(deep+1,n);
v[i] = 0;
}
}
}
int main(){
int n,i;
while(scanf("%d",&n)!=EOF){
for(i = 0;i < n;i++){
v[i] = 0;
scanf("%d",&num[i]);
}
now = 0;
sort(num,num+n);
DFS(0,n);
}
return 0;
}
//G [1120] Reimu's Teleport
//线段树 成段替换 区间求和
/*
解题思路
线段树叶子结点中
0表示top
1表示向右
1000000表示向左
查询的结果ans
向左：ans/1000000
向右：ans%1000000
向上：区间长度减去上面那两个
*/
#include<stdio.h>
#include<string.h>
#define N 100005
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
//#define int64 __int64
#define int64 long long
int m,n;
int64 sum[N<<2];
int64 add[N<<2];
void pushup(int rt){
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void pushdown(int rt,int m){
if(add[rt]){
add[rt<<1] = add[rt];
add[rt<<1|1] = add[rt];
sum[rt<<1] = add[rt] * (m-(m>>1));
sum[rt<<1|1] = add[rt] * (m>>1);
add[rt] = 0;
}
}
void update(int rt, int l,int r, int L,int R,int c){
if(L <= l && R >= r){
add[rt] = c;
sum[rt] = (int64)c * (r-l+1);
return ;
}
pushdown(rt,r-l+1);
int mid = (l + r) >> 1;
if(L <= mid) update(lson,L,R,c);
if(R > mid) update(rson,L,R,c);
pushup(rt);
}
int64 query(int rt,int l,int r, int L,int R){
if(L <= l && R >= r)
return sum[rt];
pushdown(rt,r-l+1);
int mid = ( r + l) >>1;
int64 res = 0;
if(L <= mid) res += query(lson,L,R);
if(R > mid) res += query(rson,L,R);
return res;
}
void print(int n){
int i;
for(i = 0; i <= n; ++i)
printf("sum[%d]: %I64d\n",i,sum[i]);
puts("");
}
int main(){
int i;
int a,b;
char op[5];
while(scanf("%d %d",&m,&n)!=EOF){
memset(sum,0,sizeof(sum));
memset(add,0,sizeof(add));
//print(30);
for(i = 1; i <= m; ++i){
scanf("%s %d %d",op,&a,&b);
if(op[0] == 'F'){
if(a < b)
update(1,1,n,a,b,1);
else
update(1,1,n,b,a,1000000);
//print(30);
}
else{
int64 ans = query(1,1,n,a,b);
int64 l = ans/1000000;
int64 r = ans%1000000;
int64 t = b-a+1-l-r;
//printf("%I64d %I64d %I64d\n",l,t,r);
printf("%lld %lld %lld\n",l,t,r);
}
}
}
return 0;
}
//I [1122] Shameimaru's Candid Camera 【N,M 给的是相反的 输出时 每组数据间要加空行】
#include<iostream>
using namespace std;
#define N 505
char map[N][N];
int ans[N][N];
int dir[8][2]={-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1};
int n,m;
bool check(int x,int y){
if(x >= 1 && x <= n && y >= 1 && y <= m)
return true;
return false;
}
int main(){
int i,j,k,ca=1;
int x,y;
memset(map,0,sizeof(map));
memset(ans,0,sizeof(ans));
while(scanf("%d %d",&m,&n)!=EOF){
if(ca != 1)
printf("\n");
else ca++;
for(i = 1; i <= n; ++i)
scanf("%s",map[i]+1);
for(i = 1; i <= n; ++i)
for(j = 1; j <= m; ++j){
if(map[i][j] != '*'){
ans[i][j] = 0;
for(k = 0; k <8; ++k){
x = i + dir[k][0];
y = j + dir[k][1];
if(check(x,y) && map[x][y] =='*')
ans[i][j]++;
}
}
}
for(i = 1; i <= n; ++i){
for(j = 1; j <= m; ++j){
if(map[i][j] == '*')
printf("*");
else if(ans[i][j] == 0)
printf("-");
else
printf("%d",ans[i][j]);
}
printf("\n");
}
}
return 0;
}
分享到：
相关推荐
2012浙江省赛解题报告大全，非常经典的解题报告，对OIer/ACMer有很大帮助。
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
acm 解题报告，强烈推荐acm 解题报告
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
这是一位ACM大牛写的《2008ACM浙江省赛解题报告》，希望对ACM爱好者有帮助。
第五届北航程序设计大赛网络赛 解题报告。。。。。。。。。。。。。。
这是杭电OJ上某些题的解题报告，后续还有上传很多！
北大pku poj 3070 Fibonacci解题报告源代码 - acm解题报告
2018 年（第四届）全国网络空间安全大赛 线上赛解题报告 主办单位：中国兵工学会信息安全与对抗技术专业委员会 承办单位：西安工业大学 协办单位：西安胡门网络技术有限公司
zju部分 解题报告zju部分 解题报告
北大poj解题报告,希望能帮到软件工程的同学,每天一道,持之以恒,熟能生巧,与您共勉!
买水果用线段树或树状数组，叶节点维护每种价格水果的总价，从编号为 1的水果到编号为 n 的水果，每次查询小于当前水果单价减 1 的总价，再给当前单价的水果总价加
宁波市二十八届中小学生计算机竞赛初中组解题报告.pdf
全国中级教练员，王祺磊老师所写的NOIP普及组2010年解题报告。欢迎下载传播
noip2013解题报告,比较详细的解析说明题意
信息学奥赛的重要资料。对于爱好信息学奥赛的青少年而言，此报告十分难得。
解题报告， sdut 2107 自己写的代码、 欢迎指正 、、、、、、、
NOIP2013提高组解题报告
11111111111111111111111111111111111111111111111111111111111111
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告