本渣渣很荣幸出了这次校赛的题，题目相对都比较简单，没有任何算法题，都是暴力可以过的(除了F题需要些技巧，不过都是常用的技巧)。
先放一个所有题目的链接: 2015 ZJBTI
============================================================
这题没什么好说吧，就为了保证能送出U盘，直接上代码
C++：
#include <cstdio>
using namespace std;
int main()
{
#ifdef SHY
freopen("e:\\1.txt", "r", stdin);
#endif
int t;
scanf("%d%*c", &t);
while(t--)
{
int a,b;
scanf("%d %d%*c", &a, &b);
if(a >= b) printf("%d\n", a-b);
else printf("0\n");
}
return 0;
}
Java
import java.io.*;
import java.util.*;
public class Main
{
public static void main(String args[]) throws Exception
{
Scanner in=new Scanner(System.in);
int t = in.nextInt();
for(int i = 0; i < t; i++)
{
int a = in.nextInt(),b = in.nextInt();
if(a >= b) System.out.println(a-b);
else System.out.println("0");
}
}
}
============================================================
可以直接模拟双方轮流攻击，先算好双方攻击对方的伤害(就是A题的求法),然后记录下双方生命值，模拟轮流攻击，谁先死就输了，代码:
C++
#include <cstdio>
using namespace std;
int hp[2], s[2];//hp[]表示双方生命,s[]表示双方攻击对方造成的伤害
bool ok()//模拟计算谁的生命值先<=0就输了
{
int a = 0;
while(hp[0] > 0 && hp[1] > 0)
{
hp[a^1] -= s[a];
a ^= 1;//a^1就是轮流攻击，不会^的可以百度学习下位运算,或者你可以用其他方法替换掉，自己想
}
if(hp[0] <= 0) return false;
return true;
}
int main()
{
#ifdef SHY
freopen("e:\\1.txt", "r", stdin);
#endif
int t;
scanf("%d%*c", &t);
while(t--)
{
int p[2],d[2];
for(int i = 0;i < 2; i++) scanf("%d %d %d%*c", &p[i],&d[i],&hp[i]);
for(int i = 0;i < 2; i++) s[i] = p[i]>=d[i^1]?p[i]-d[i^1]:0;
if(ok()) puts("victory");
else puts("failure");
}
return 0;
}
其实还有一种想当简单的和快速的方法：不难发现，只要算出我方杀死敌人需要攻击几次t[0]以及敌人杀死我方需要攻击几次t[1],如果t[0]<=t[1]就是我方胜利，为什么是<=呢？因为我方先攻击的，代码如下:
C++：
#include <cstdio>
using namespace std;
const int INF = 0x3f3f3f3f;
int hp[2], s[2];
int main()
{
#ifdef SHY
freopen("e:\\1.txt", "r", stdin);
//freopen("e:\\out.txt", "w", stdout);
#endif
int t;
scanf("%d%*c", &t);
while(t--)
{
int p[2],d[2],t[2];
for(int i = 0; i < 2; i++) scanf("%d %d %d%*c", &p[i],&d[i],&hp[i]);
for(int i = 0; i < 2; i++) s[i] = p[i]>=d[i^1]?p[i]-d[i^1]:0;//算出攻击对方的伤害
for(int i = 0; i < 2; i++)//算出杀死对方需要攻击几次
{
if(s[i])
t[i] = hp[i^1]/s[i]+bool(hp[i^1]%s[i]);
else//如果伤害为0就无法杀死对方,题目保证了不会存在两个都为0的情况，所以一定有解
t[i] = INF;
}
if(t[0] <= t[1]) puts("victory");
else puts("failure");
}
return 0;
}
Java：
import java.io.*;
import java.util.*;
public class Main
{
public static void main(String args[]) throws Exception
{
Scanner in=new Scanner(System.in);
int c = in.nextInt(), INF = 0x3f3f3f3f;
while(c > 0)
{
int hp[] = new int[2], s[] = new int[2];//hp自己血量,s攻击对方造成的伤害
int p[] = new int[2], d[] = new int[2], t[] = new int[2];//p力量，d防御，t杀死对方需要攻击几次
//读入
for(int i = 0; i < 2; i++)
{
p[i] = in.nextInt();
d[i] = in.nextInt();
hp[i] = in.nextInt();
}
//算出攻击对方的伤害
for(int i = 0; i < 2; i++) s[i] = p[i]>=d[i^1]?p[i]-d[i^1]:0;//这里的i^1就是对方
for(int i = 0; i < 2; i++)//算出杀死对方需要攻击几次
{
if(s[i] > 0)
t[i] = hp[i^1]/s[i]+((hp[i^1]%s[i])>0?1:0);
else//如果伤害为0就无法杀死对方,题目保证了不会存在两个都为0的情况，所以一定有解
t[i] = INF;
}
if(t[0] <= t[1]) System.out.println("victory");
else System.out.println("failure");
c--;
}
}
}
============================================================
用一个sum[]记录每个人拥有的钱，每条消费清单A,B为sum[A] -= B;
算完M条清单后，这时的sum就是最后所有人剩下的钱，扫描一边记录下最大值的编号就可以了
C++：
#include <cstdio>
using namespace std;
const int INF = 0x3f3f3f3f, MAXN = 10000+10;
int sum[MAXN];
int main()
{
#ifdef SHY
freopen("e:\\1.txt", "r", stdin);
//freopen("e:\\out.txt", "w", stdout);
#endif
int t;
scanf("%d%*c", &t);
while(t--)
{
int n,m;
scanf("%d %d%*c", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d%*c", &sum[i]);
for(int i = 0; i < m; i++)
{
int a,b;
scanf("%d %d%*c", &a, &b);
sum[a] -= b;
}
int mx = -INF,id;
for(int i = 1; i <= n; i++)
{
if(mx < sum[i])
{
mx = sum[i];
id = i;
}
}
printf("%d\n", id);
}
return 0;
}
Java：
import java.io.*;
import java.util.*;
public class Main
{
static int sum[] = new int[10000+10];//表示每个人有多少钱
public static void main(String args[]) throws Exception
{
Scanner in=new Scanner(System.in);
int t = in.nextInt(), INF = 0x3f3f3f3f;
while(t-- > 0)
{
int n = in.nextInt(), m = in.nextInt();
//初始现金
for(int i = 1; i <= n; i++) sum[i] = in.nextInt();
//m条消费
for(int i = 0; i < m; i++)
{
int a = in.nextInt(), b = in.nextInt();
sum[a] -= b;
}
int mx = -INF,id = 1;//统计最大值和最大值编号
for(int i = 1; i <= n; i++)
{
if(mx < sum[i])
{
mx = sum[i];
id = i;
}
}
System.out.println(id);
}
}
}
============================================================
就是每读一行字符串，倒序输出就好了，注意下数字后面的’\n’就行了(本来题目中没提示，怕错太多所以写出来了)
C++：
#include <cstdio>
using namespace std;
const int MAXN = 1000+10;
char a[MAXN];
int main()
{
#ifdef SHY
freopen("e:\\1.txt", "r", stdin);
//freopen("e:\\out.txt", "w", stdout);
#endif
int t;
scanf("%d%*c", &t);
while(t--)
{
int n,m;
scanf("%d %d%*c", &n, &m);
for(int i = 0; i < n; i++)
{
gets(a);
for(int j = m-1; j >= 0; j--) putchar(a[j]);
putchar('\n');
}
}
return 0;
}
Java:
import java.io.*;
import java.util.*;
public class Main
{
public static void main(String args[]) throws Exception
{
Scanner in=new Scanner(System.in);
int t = in.nextInt();
while(t-- > 0)
{
int n = in.nextInt(), m = in.nextInt();
in.nextLine();//注意读掉整数后面的一个'\n'符号
for(int i = 0; i < n; i++)
{
String a = in.nextLine();
for(int j = m-1; j >= 0; j--) System.out.print(a.charAt(j));
System.out.println();
}
}
}
}
============================================================
这题应该是线段树的区间更新区间查询的标准题，但是为了简化这里的数据量n*m的暴力都可以过：
用一个sum[]记录当前站点有多少人则：
对于ADD a b:就是sum[a~b-1]都加1;
对于DEL a b:就是sum[a~b-1]都减1;
对于QUERY a b:就是求出sum[a~b-1]中的最大值就是实际售出的车票，想想是不是这样
这样n<=10000,m<=1000,最坏的时间复杂度是n*m=10^7,可以1秒左右跑完；
c++暴力代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 10000+10;
int sum[MAXN];
/*对应三种操作*/
void add(int x, int y)
{
for(int i = x; i <= y; i++) sum[i]++;
}
int query(int x, int y)
{
int mx = 0;
for(int i = x; i <= y; i++) mx = max(mx,sum[i]);
return mx;
}
void del(int x, int y)
{
for(int i = x; i <= y; i++) sum[i]--;
}
int main()
{
#ifdef SHY
freopen("e:\\1.txt", "r", stdin);
//freopen("e:\\out.txt", "w", stdout);
#endif
int t,count = 0;
scanf("%d%*c", &t);
while(t--)
{
int n,m;
scanf("%d %d", &n, &m);
memset(sum,0,sizeof(sum));
char op[10];
int a,b;
printf("Motorcar#%d\n", ++count);
for(int i = 0; i < m; i++)
{
scanf("%s %d %d", op, &a, &b);
b--;//保证区间[a,b-1]
if(!strcmp(op,"ADD")) add(a,b);
else if(!strcmp(op,"QUERY")) printf("%d\n", query(a,b));
else del(a,b);
}
}
return 0;
}
JAVA暴力代码:
import java.io.*;
import java.util.*;
public class Main
{
static int sum[] = new int[10000+10];
public static void add(int a, int b){
for(int i = a; i <= b; i++) sum[i]++;
}
public static void del(int a, int b){
for(int i = a; i <= b; i++) sum[i]--;
}
public static int query(int a, int b){
int mx = -1;
for(int i = a; i <= b; i++){
if(mx < sum[i])
mx = sum[i];
}
return mx;
}
public static void main(String args[]) throws Exception
{
Scanner in=new Scanner(System.in);
int t = in.nextInt();
int count = 0;
String op;
for(int i = 0; i < t; i++){
int n = in.nextInt(), m = in.nextInt();
for(int j = 1;j <= n; j++) sum[j] = 0;
System.out.println("Motorcar#"+(++count));
for(int j = 0; j < m; j++){
op = in.next();
int x = in.nextInt(), y = in.nextInt();
if(op.charAt(0) == 'A'){
add(x,y-1);
}
else if(op.charAt(0) == 'Q'){
System.out.println(query(x,y-1));
}
else{
del(x,y-1);
}
}
}
}
}
而标准的算法应该是用线段树n*log(n)的时间复杂度，在这里是10^5级别的，显然快很多，我只要把m加大上面的算法马上就超时了，不会线段树的可以去学习下这个数据结构(我这里线段树的写法可能和网上的有很大不同，这个用了剩内存的技巧):
C++:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define id(x,y) ((x)+(y)|(x)!=(y))
const int MAXN = 10000+10;
int mx[MAXN<<1], add[MAXN<<1];//add[]是lazy标记
void push_up(int x, int y, int m)
{
mx[id(x,y)] = max(mx[id(x,m)],mx[id(m+1,y)]);
}
void push_down(int x, int y, int m)
{
int u = id(x,y), lc = id(x,m), rc = id(m+1,y);
if(add[u])
{
add[lc] += add[u];
mx[lc] += add[u];
add[rc] += add[u];
mx[rc] += add[u];
add[u] = 0;
}
}
int ql, qr, v;
void update(int x, int y)
{
if(ql <= x && y <= qr)
{
mx[id(x,y)] += v;
add[id(x,y)] += v;
return;
}
int m = (x+y)>>1;
push_down(x,y,m);
if(ql <= m) update(x,m);
if(qr > m) update(m+1,y);
push_up(x,y,m);
}
int query(int x, int y)
{
if(ql <= x && y <= qr)
return mx[id(x,y)];
int m = (x+y)>>1, ans = -1;
push_down(x,y,m);
if(ql <= m) ans = max(ans,query(x,m));
if(qr > m) ans = max(ans,query(m+1,y));
return ans;
}
int main()
{
#ifdef SHY
freopen("e:\\1.txt", "r", stdin);
#endif
int t, count = 0;
scanf("%d%*c", &t);
while(t--)
{
int n,m;
scanf("%d %d%*c", &n, &m);
n--;
char op[10];
memset(mx,0,sizeof(mx));
memset(add,0,sizeof(add));
printf("Motorcar#%d\n",++count);
for(int i = 0; i < m; i++)
{
scanf("%s %d %d%*c", op, &ql, &qr);
qr--;
if('A' == op[0])
{
v = 1;
update(1,n);
}
else if('Q' == op[0]) printf("%d\n", query(1,n));
else
{
v = -1;
update(1,n);
}
}
}
return 0;
}
============================================================
这个是相对来说最难一点的题，其实也很简单，只要用邻接表存图(邻接矩阵会超内存)来存人际关系。这个可以C++ STL里面的vector,或者任何语言通用的链式前向星存图的方法(下面用JAVA实现的)
然后是空间关系，如果每次都把两个人之间的所有距离之和加起来计算的会超时，因为复杂度变成n^2了，而N是10^5，所以不能这么算，其实只要用sum[]存从左到右的前缀和(即sum[i] = sum[i-1]+d[i])，则这样的话计算任意两个人A,B之间距离只要计算sum[B]-sum[A-1]就可以啦，复杂度只要0(1),再乘上N，复杂度还是N。
最后还有个问题就是排序必须使用快排等n*log(n)的算法，不然铁定超时，最简单的当然是用C/C++中的sort()或者qsort()函数,或者JAVA里面的Arrays.sort();
C++版：
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 100000+10;
vector<int> g[MAXN];
int sum[MAXN], dis[MAXN];
int main()
{
#ifdef SHY
freopen("e:\\1.txt", "r", stdin);
//freopen("e:\\out.txt", "w", stdout);
#endif
int t;
scanf("%d%*c", &t);
sum[0] = 0;
while(t--)
{
int n,m,p,k, d;
scanf("%d %d %d %d%*c", &n, &m, &p, &k);
for(int i = 1; i < n; i++) scanf("%d%*c", &d), sum[i] = sum[i-1]+d;
for(int i = 1; i <= n; i++) g[i].clear();
while(m--)
{
int a,b;
scanf("%d %d%*c", &a, &b);
g[a].push_back(b);
g[b].push_back(a);
}
int cnt = 0;
for(int i = 0; i < g[p].size(); i++)
{
int v = g[p][i];
if(v > p) dis[cnt++] = sum[v-1]-sum[p-1];
else dis[cnt++] = sum[p-1]-sum[v-1];
}
sort(dis,dis+cnt);
if(cnt < k) puts("-1");
else printf("%d\n", dis[k-1]);
}
return 0;
}
JAVA链式前向星版:
import java.io.*;
import java.util.*;
public class Main
{
static int MAXN = 200000+10;
static int sum[] = new int[MAXN];
static int d[] = new int[MAXN];
static int head[] = new int[MAXN];//链式前向星
static int next[] = new int[MAXN];//链式前向星
static int to[] = new int[MAXN];//链式前向星
static int ans[] = new int[MAXN];
static int tol;//链式前向星
public static void add_edge(int u, int v){//链式前向星
next[tol] = head[u];
to[tol] = v;
head[u] = tol++;
}
public static void main(String args[]) throws Exception
{
Scanner in=new Scanner(System.in);
int t = in.nextInt();
sum[0] = 0;
for(int i = 0; i < t; i++)
{
int n = in.nextInt(),m = in.nextInt(),p = in.nextInt(),k = in.nextInt();
for(int j = 1; j < n; j++)
{
d[j] = in.nextInt();
sum[j] = d[j]+sum[j-1];
}
tol = 0;
for(int j = 1; j <= n; j++){
head[j] = -1;
}
for(int j = 1; j <= m; j++)
{
int a = in.nextInt(),b = in.nextInt();
add_edge(a,b);
add_edge(b,a);
}
int cnt = 0;
for(int j = head[p]; -1 != j; j = next[j]){
int v = to[j];
if(v < p) ans[cnt++] = sum[p-1]-sum[v-1];
else ans[cnt++] = sum[v-1]-sum[p-1];
}
Arrays.sort(ans,0,cnt);
if(cnt < k) System.out.println("-1");
else System.out.println(ans[k-1]);
}
}
}
============================================================
题意是十佳歌手比赛，有N个评委给出N个成绩，选手得分为去掉一个最高分和一个最低分后的总分，输出这个总分。
知道题意了应该不用说什么了吧，超级简单，代码：
C++:
#include <cstdio>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
int main()
{
#ifdef SHY
freopen("e:\\1.txt", "r", stdin);
freopen("e:\\out.txt", "w", stdout);
#endif
int t;
scanf("%d%*c", &t);
while(t--)
{
int n, mx = -1, mi = INF, sum = 0;
scanf("%d%*c", &n);
for(int i = 0; i < n; i++)
{
int x;
scanf("%d%*c", &x);
mx = max(x, mx);
mi = min(x,mi);
sum += x;
}
printf("%d\n", sum-mi-mx);
}
return 0;
}
Java:
import java.io.*;
import java.util.*;
public class Main
{
public static void main(String args[]) throws Exception
{
Scanner in=new Scanner(System.in);
int t = in.nextInt(), INF = 0x3f3f3f3f;
while(t-- > 0)
{
int n = in.nextInt(), mx = -1, mi = INF, sum = 0;
for(int i = 0; i < n; i++)
{
int x = in.nextInt();
sum += x;
if(mx < x) mx = x;
if(mi > x) mi = x;
}
System.out.println(sum-mx-mi);
}
}
}
============================================================
题意是给你一篇文章，只有大小写字母还有空格和回车，求出有多少个不同的单词，数据量想当小，可以直接暴力，每次出现一个单词就扫描前面出现过的单词，如果存在则忽略，如果没出现过就存下来，答案计数+1。
但是这里用的是另外一种比较高效的方法，用C++的map来替代上面的循环判重，复杂度是O(n*log(n))的
这里用到了C++的STL容器，不会C++容器的点这里，Java中的容器其实也是类似的，一通百通，当然这题你完全可以不用容器(全部手写，就是代码长点，效率一般比STL高，但复杂度级别是一样的)
代码：
C++:
#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 1000+10;
char a[MAXN];
map<string, int> vis;
int main()
{
#ifdef SHY
freopen("e:\\1.txt", "r", stdin);
#endif
vis.clear();
while(~scanf("%s", a))
vis[a] = true;
printf("%d\n", vis.size());
return 0;
}
Java:
import java.io.*;
import java.util.*;
public class Main
{
public static void main(String args[]) throws Exception
{
Scanner in=new Scanner(System.in);
TreeMap<String,Integer> vis = new TreeMap<String,Integer>();
vis.clear();
while(in.hasNext()){
String a = in.next();
vis.put(a,1);
}
System.out.println(vis.size());
}
}
这题还可以用HASH或者字典树来解，都是比较高效的(其实我只放了不到100个单词，每个单词的长度都不超过15，所以随便怎么写都很快)
