感谢本次验题人:诸日强。这次出的8题中7题都是比较简单的，6题都是跟着题意搞搞就好了，G题稍微思考下也能很容易想到，只有C是为了防AK而设的。本来B题是现在OJ上的1136题，由于诸日强说有点难度(可能都不会用STL)，所以决定换掉了，还有E题原本Ai的范围是10^9不能直接使用数组下标，在诸日强的建议下改成了200000。
题解目录:
【A题】
用一个变量st指向每次相同的字符出现的最左边的位置，那么只要找出max{i-st}即可。这样复杂度O(n)。
C++ O(n)代码:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3000+10;
char a[MAXN];
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
int n;
scanf("%d%s", &n,a);
int ans = 1,la = 0;
for(int i = 1; i < n; i++)
{
if(a[i] != a[i-1]) la = i;
ans = max(ans,i-la+1);
}
printf("%d\n", ans);
}
return 0;
}
当然由于字符串长度只有3000，你可以用两层循环暴力找，复杂度O(N^2)
O(N^2):
C++:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3000+10;
char a[MAXN];
int get_ans(int s, int n)
{
int ans = 0;
for(int i = s; i < n; i++)
{
if(a[s] == a[i]) ans++;
else break;
}
return ans;
}
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
int n;
scanf("%d%s", &n,a);
int ans = 1;
for(int i = 0; i < n; i++)
ans = max(ans,get_ans(i,n));
printf("%d\n", ans);
}
return 0;
}
Java：
import java.io.*;
import java.util.*;
public class Main
{
static char a[] = new char[3000+10];
public static int get_ans(int s, int n)
{
int ans = 0;
for(int i = s; i < n; i++)
{
if(a[s] == a[i]) ans++;
else break;
}
return ans;
}
public static void main(String args[]) throws Exception
{
Scanner cin=new Scanner(System.in);
int t = cin.nextInt();
for(int c = 0; c < t; c++)
{
int n = cin.nextInt();
a = cin.next().toCharArray();
int ans = 1;
for(int i = 0;i < n;i++)
{
int tmp = get_ans(i,n);
if(ans < tmp)
ans = tmp;
}
System.out.println(ans);
}
}
}
【B题】
跟着题意来就好了。每次超过100，等级+1，记得经验归零。不需要给代码了吧。
【C题】
本次比赛最难的一题，这里给出三种解法:
【一】LCA(最近公共祖先)+可持久化线段树(函数式线段树/主席树)：从根结点1开始DFS的同时在树上建立可持久化线段树，维护值域，然后任意两点(x,y)的路径就是x+y-LCA(x,y)-fa[LCA(x,y)]。查询的时候找最大最小值就可以，就是查找第K大类似的。复杂度O(N*log(N))。关于LCA和可持久化线段树可以百度/谷歌学习。
C++:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 50000+10, MAXM = MAXN, M = 20*MAXN;
int a[MAXN],head[MAXN],tol,nxt[MAXM],to[MAXM];
inline void add_edge(int u, int v)
{
nxt[tol] = head[u],to[tol] = v;
head[u] = tol++;
}
int cnt, ft[MAXN], fa[MAXN],d[MAXN<<1],num[MAXN<<1];//d数组点数为2*n-1
int rt[MAXN],lc[M],rc[M],sum[M],all,mxa;
void insert(int &u, int x, int y, int p)//可持久化线段树插入结点
{
lc[++all] = lc[u],rc[all] = rc[u],sum[all] = sum[u]+1;
u = all;
if(x == y) return;
int m = (x+y)>>1;
if(p <= m) insert(lc[u],x,m,p);
else insert(rc[u],m+1,y,p);
}
void dfs(int u, int deep)//找到每个点进入和返回时的所有ft,d,num
{
ft[u] = cnt;
d[cnt] = deep, num[cnt++] = u;
rt[u] = rt[fa[u]];
insert(rt[u],1,mxa,a[u]);
for(int i = head[u]; ~i; i = nxt[i])
{
int v = to[i];
//if(fa == v) continue;
fa[v] = u;
dfs(v,deep+1);
d[cnt] = deep, num[cnt++] = u;
}
}
int dp[MAXN<<1][21], dp_num[MAXN<<1][21];//dp_num记录dp对应的点的编号
void st_init()
{
rep(i,0,cnt) dp[i][0] = d[i], dp_num[i][0] = num[i];
for(int j = 1; (1<<j) <= cnt; j++)
{
for(int i = 0; i+(1<<j)-1 < cnt; i++)
{
if(dp[i][j-1] < dp[i+(1<<(j-1))][j-1])
{
dp[i][j] = dp[i][j-1];
dp_num[i][j] = dp_num[i][j-1];
}
else
{
dp[i][j] = dp[i+(1<<(j-1))][j-1];
dp_num[i][j] = dp_num[i+(1<<(j-1))][j-1];
}
}
}
}
int st_query(int x, int y)//查询d[x~y]中最小值对应的点编号
{
if(x > y) swap(x,y);
int k = 0;
while((1<<(k+1)) <= y-x+1) k++;
if(dp[x][k] <= dp[y-(1<<k)+1][k]) return dp_num[x][k];
return dp_num[y-(1<<k)+1][k];
}
void init(int rt)//初始化O(n*log(n))
{
cnt = all = fa[1] = 0;
dfs(rt,0);
st_init();
}
int lca_query(int x, int y)//x,y的LCA, O(1)
{
return st_query(ft[x],ft[y]);
}
int find_mi(int lca, int lcaf,int tx, int ty, int x, int y)
{
if(x == y) return x;
int m = (x+y)>>1;
int d = sum[lc[tx]]+sum[lc[ty]]-sum[lc[lca]]-sum[lc[lcaf]];
if(d) return find_mi(lc[lca],lc[lcaf],lc[tx],lc[ty],x,m);
return find_mi(rc[lca],rc[lcaf],rc[tx],rc[ty],m+1,y);
}
int find_mx(int lca, int lcaf,int tx, int ty, int x, int y)
{
if(x == y) return x;
int m = (x+y)>>1;
int d = sum[rc[tx]]+sum[rc[ty]]-sum[rc[lca]]-sum[rc[lcaf]];
if(d) return find_mx(rc[lca],rc[lcaf],rc[tx],rc[ty],m+1,y);
return find_mx(lc[lca],lc[lcaf],lc[tx],lc[ty],x,m);
}
int query(int x, int y)//本题询问
{
int lca = lca_query(x,y);
return find_mx(rt[lca],rt[fa[lca]],rt[x],rt[y],1,mxa)-find_mi(rt[lca],rt[fa[lca]],rt[x],rt[y],1,mxa);
}
int main()
{
#ifdef SHY
freopen("d:\\1.txt", "r", stdin);
freopen("d:\\out.txt", "wb", stdout);
#endif
int t,count = 0;
scanf("%d", &t);
while(t--)
{
int n;
scanf("%d", &n);
mxa = 0;
repe(i,1,n) scanf("%d", &a[i]),mxa = max(mxa,a[i]);
clc(head,-1);tol = 0;
rep(i,1,n)
{
int u,v;
scanf("%d%d", &u,&v);
add_edge(u,v);
}
init(1);
int q;
scanf("%d", &q);
printf("Case #%d:\n",++count);
while(q--)
{
int x,y;
scanf("%d%d", &x, &y);
printf("%d\n", query(x,y));
}
}
return 0;
}
Java:
import java.io.*;
import java.util.*;
public class Main
{
final static int MAXN = 50000+10, MAXM = MAXN,M = 50*MAXN;
static int a[] = new int [MAXN],head[] = new int [MAXN],tol,nxt[] = new int [MAXN],to[] = new int [MAXN];
public static void add_edge(int u, int v)
{
nxt[tol] = head[u];
to[tol] = v;
head[u] = tol++;
}
static int cnt, ft[] = new int [MAXN], fa[] = new int [MAXN],d[] = new int [MAXN<<1],num[] = new int [MAXN<<1];
static int rt[] = new int [MAXN],lc[] = new int [M],rc[] = new int [M],sum[] = new int [M],all,mxa;
public static void insert(int u, int x, int y, int p)//可持久化线段树插入结点
{
lc[++all] = lc[u];rc[all] = rc[u];sum[all] = sum[u]+1;
u = all;
if(x == y) return;
int m = (x+y)>>1;
if(p <= m)
{
insert(lc[u],x,m,p);
lc[u] = u+1;
}
else
{
insert(rc[u],m+1,y,p);
rc[u] = u+1;
}
}
static Stack<Integer> s = new Stack<Integer>();
static int vis[] = new int[MAXN],deep[] = new int[MAXN],n;
public static void dfs(int uu)
{
while(!s.empty()) s.pop();
for(int i = 0; i <= n; i++) vis[i] = 0;
s.push(uu);
while(!s.empty())
{
int u = s.peek();
if(0 != vis[u])//从儿子结点返回
{
s.pop();
d[cnt] = deep[fa[u]];
num[cnt++] = fa[u];
continue;
}
/*第一次进入结点u*/
ft[u] = cnt;
d[cnt] = deep[u];num[cnt++] = u;
vis[u] = 1;
rt[u] = rt[fa[u]];
int tmp = all;
insert(rt[u],1,mxa,a[u]);
rt[u] = tmp+1;
for(int i = head[u]; -1 != i; i = nxt[i])
{
int v = to[i];
fa[v] = u;deep[v] = deep[u]+1;
s.push(v);
}
}
}
static int dp[][] = new int[MAXN<<1][21], dp_num[][] = new int[MAXN<<1][21];//dp_num记录dp对应的点的编号
public static void st_init()
{
for(int i = 0; i < cnt; i++)
{
dp[i][0] = d[i]; dp_num[i][0] = num[i];
}
for(int j = 1; (1<<j) <= cnt; j++)
{
for(int i = 0; i+(1<<j)-1 < cnt; i++)
{
if(dp[i][j-1] < dp[i+(1<<(j-1))][j-1])
{
dp[i][j] = dp[i][j-1];
dp_num[i][j] = dp_num[i][j-1];
}
else
{
dp[i][j] = dp[i+(1<<(j-1))][j-1];
dp_num[i][j] = dp_num[i+(1<<(j-1))][j-1];
}
}
}
}
public static int st_query(int x, int y)//查询d[x~y]中最小值对应的点编号
{
if(x > y) {x ^= y;y ^= x; x^= y;}
int k = 0;
while((1<<(k+1)) <= y-x+1) k++;
if(dp[x][k] <= dp[y-(1<<k)+1][k]) return dp_num[x][k];
return dp_num[y-(1<<k)+1][k];
}
public static void init(int rt)//初始化O(n*log(n))
{
cnt = all = fa[1] = deep[1] = 0;
dfs(rt);
st_init();
}
public static int lca_query(int x, int y)//x,y的LCA, O(1)
{
return st_query(ft[x],ft[y]);
}
public static int find_mi(int lca, int lcaf,int tx, int ty, int x, int y)
{
if(x == y) return x;
int m = (x+y)>>1;
int d = sum[lc[tx]]+sum[lc[ty]]-sum[lc[lca]]-sum[lc[lcaf]];
if(d != 0) return find_mi(lc[lca],lc[lcaf],lc[tx],lc[ty],x,m);
return find_mi(rc[lca],rc[lcaf],rc[tx],rc[ty],m+1,y);
}
public static int find_mx(int lca, int lcaf,int tx, int ty, int x, int y)
{
if(x == y) return x;
int m = (x+y)>>1;
int d = sum[rc[tx]]+sum[rc[ty]]-sum[rc[lca]]-sum[rc[lcaf]];
if(d != 0) return find_mx(rc[lca],rc[lcaf],rc[tx],rc[ty],m+1,y);
return find_mx(lc[lca],lc[lcaf],lc[tx],lc[ty],x,m);
}
public static int query(int x, int y)//本题询问
{
int lca = lca_query(x,y);
return find_mx(rt[lca],rt[fa[lca]],rt[x],rt[y],1,mxa)-find_mi(rt[lca],rt[fa[lca]],rt[x],rt[y],1,mxa);
}
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String args[]) throws Exception
{
int t = Integer.parseInt(in.readLine());
for(int c = 0; c < t; c++)
{
n = Integer.parseInt(in.readLine());
mxa = 0;
StringTokenizer st = new StringTokenizer(in.readLine());
for(int i = 1; i <= n; i++)
{
a[i] = Integer.valueOf(st.nextToken());
if(mxa < a[i]) mxa = a[i];
head[i] = -1;
}
tol = 0;
for(int i = 1; i < n; i++)
{
st = new StringTokenizer(in.readLine());
int u = Integer.valueOf(st.nextToken());
int v = Integer.valueOf(st.nextToken());
add_edge(u,v);
}
init(1);
int q = Integer.parseInt(in.readLine());
out.write("Case #"+(c+1)+":\n");
for(int i = 0; i < q; i++)
{
st = new StringTokenizer(in.readLine());
int x = Integer.valueOf(st.nextToken());
int y = Integer.valueOf(st.nextToken());
out.write(query(x,y)+"\n");
}
}
out.flush();
}
}
【二 】树链剖分:维护最大值和最小值即可，答案就是他们差。关于树链剖分不会的请百度/谷歌学习。复杂度O( N*log(N)*log(N) )；虽然复杂度比可持久化线段树高一个log(N)，但是常数要小很多，在这个数据量下反而更快。
C++代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 50000+10, MAXM = 50000+10;
int head[MAXN], tol, nxt[MAXM], to[MAXM];
int a[MAXN];//每个点初始权值
inline void add_edge(int u, int v)
{
nxt[tol] = head[u], to[tol] = v;
head[u] = tol++;
}
struct TCP{
private:
int fa[MAXN];//fa[u]表示u的父亲
int dep[MAXN];//dep[u]表示u的深度
int sz[MAXN];//sz[u]表示以u为根的子树有几个结点
int son[MAXN];//son[u]表示u的所有儿子结点中sz[]最大的那个点(重儿子)
int top[MAXN];//top[u]表示u所在的链的顶端节点
int tree[MAXN];//tree[u]表示节点u在线段树中的编号
int pre[MAXN];//pre[x]表示线段树中编号为x的点在树中的点(和tree相反)
int cnt;//线段树中点的数量(其实就是n)
void dfs1(int u)//预处理fa[],dep[],sz[],son[]
{
int num = 0;
sz[u] = 1;
for(int i = head[u]; ~i; i = nxt[i])
{
int v = to[i];
if(v == fa[u]) continue;
fa[v] = u;dep[v] = dep[u]+1;
dfs1(v);
if(sz[v] > num) num = sz[v], son[u] = v;
sz[u] += sz[v];
}
}
void dfs2(int u, int num)//预处理top[],tree[],pre[]
{
tree[u] = cnt, pre[cnt++] = u,top[u] = num;
if(-1 == son[u]) return;
dfs2(son[u],num);//必须点递归重儿子，否则重链在线段树的编号会不连续
for(int i = head[u]; ~i; i = nxt[i])
{
int v = to[i];
if(v != fa[u] && son[u] != v) dfs2(v,v);
}
}
/*--线段树--s*/
int mx[MAXN<<1],mi[MAXN<<1];
inline int id(int x, int y){return x+y|x!=y;}
void bulid(int x, int y)
{
if(x == y)
{
mx[id(x,y)] = mi[id(x,y)] = a[pre[x]];
return;
}
int m = (x+y)>>1;
bulid(x,m);
bulid(m+1,y);
mx[id(x,y)] = max(mx[id(x,m)],mx[id(m+1,y)]);
mi[id(x,y)] = min(mi[id(x,m)],mi[id(m+1,y)]);
}
int qmx,qmi;
void query(int x, int y, int ql, int qr)
{
if(ql <= x && y <= qr)
{
qmx = max(qmx,mx[id(x,y)]);
qmi = min(qmi,mi[id(x,y)]);
return;
}
int m = (x+y)>>1, ans = 0;
if(ql <= m) query(x,m,ql,qr);
if(qr > m) query(m+1,y,ql,qr);
}
/*--线段树--e*/
public:
void init(int rt)
{
clc(son,-1);
dep[rt] = 0, fa[rt] = -1;
dfs1(rt);
cnt = 0;
dfs2(rt,rt);
bulid(0,cnt-1);
}
int tcp_query(int x, int y)
{
int f1 = top[x], f2 = top[y];
qmi = INF,qmx = 0;
while(f1 != f2)
{
if(dep[f1] < dep[f2]) swap(f1,f2), swap(x,y);
query(0,cnt-1,tree[f1],tree[x]);
x = fa[f1], f1 = top[x];
}
if(dep[x] > dep[y]) swap(x,y);
query(0,cnt-1,tree[x],tree[y]);
return qmx-qmi;
}
}tcp;
int main()
{
#ifdef SHY
freopen("d:\\1.txt", "r", stdin);
#endif
int t,count = 0;
scanf("%d", &t);
while(t--)
{
int n;
scanf("%d", &n);
repe(i,1,n) scanf("%d", &a[i]);
clc(head,-1);tol = 0;
rep(i,1,n)
{
int u,v;
scanf("%d%d", &u, &v);
add_edge(u,v);
}
tcp.init(1);
int q;
scanf("%d", &q);
printf("Case #%d:\n",++count);
while(q--)
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n", tcp.tcp_query(x,y));
}
}
return 0;
}
【三】Link-Cut-Tree：也可以看成动态树问题，维护最大最小值。复杂度均摊O(N*logN)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 50000+10, MAXM = 50000+10;
int par[MAXN],ch[MAXN][2],fa[MAXN],val[MAXN],mx[MAXN],mi[MAXN];
//par是真实树的父亲，fa是虚树(splay)的父亲
void init()//下标1~n
{
clc(par,0);clc(ch,0);clc(fa,0);
mi[0] = INF;
}
inline int chd(int u){return ch[fa[u]][1] == u;}
inline void setch(int f, int u, int d){ch[f][d] = u,fa[u] = f;}
inline void push_up(int u)
{
mx[u] = max(mx[ch[u][0]],max(mx[ch[u][1]],val[u]));
mi[u] = min(mi[ch[u][0]],min(mi[ch[u][1]],val[u]));
}
inline void rot(int u)
{
int d = chd(u),y = fa[u];
setch(fa[y],u,chd(y));
setch(y,ch[u][d^1],d);
setch(u,y,d^1);
push_up(y);push_up(u);
}
void splay(int u)
{
int rt = u;
while(fa[rt]) rt = fa[rt];
if(rt == u) return;
par[u] = par[rt],par[rt] = 0;
while(fa[u])
{
if(fa[fa[u]] && chd(u) == chd(fa[u])) rot(fa[u]);
rot(u);
}
}
void expose(int u)
{
for(int now = u,la = 0;now;la = now,now = par[now])
{
splay(now);
par[ch[now][1]] = now;fa[ch[now][1]] = par[la] = 0;
setch(now,la,1);
push_up(now);
}
splay(u);
}
int find_root(int u)//找到splay最左边点，即当前连通树的根
{
expose(u);
while(ch[u][0]) u = ch[u][0];
return u;
}
/*=======================有根树============================*/
bool link(int u, int v)//如果x,y不在同一颗子树中,把u所在子树接到v下面
{
//if(find_root(u) == find_root(v)) return false;
expose(u);
par[u] = v;
return true;
}
int query(int x, int y)//如果x,y在同一颗子树中，返回x,y之间路径上点权的最大值
{
//if(find_root(x) != find_root(y)) return -1;
expose(x);
for(int now = y,la = 0;now; la = now,now = par[now])
{
splay(now);
if(!par[now]) return max(mx[ch[now][1]],max(mx[la],val[now]))-min(mi[ch[now][1]],min(mi[la],val[now]));//now就是LCA(x,y)
par[ch[now][1]] = now;fa[ch[now][1]] = par[la] = 0;
setch(now,la,1);
push_up(now);
}
}
int main()
{
#ifdef SHY
freopen("d:\\1.txt", "r", stdin);
#endif
int t,count = 0;
scanf("%d", &t);
while(t--)
{
init();
int n;
scanf("%d", &n);
repe(i,1,n) scanf("%d", &val[i]),mx[i] = mi[i] = val[i];
rep(i,1,n)
{
int u,v;
scanf("%d%d", &u, &v);
link(v,u);
}
int q;
scanf("%d", &q);
printf("Case #%d:\n",++count);
while(q--)
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n", query(x,y));
}
}
return 0;
}
【D题】
应该没有人不会吧。
【E题】
一开始Ai的范围是10^9的，后来为了简单改成了2*10^5。那么就可以直接用一个2*10^5大的数组记录每个编号的出现次数，最后从头到尾扫描一遍这个数组即可。复杂度O(n)。
而当Ai为10^9的时候怎么办？只要把数组换成一颗红黑树或者HASH表即可，而这两个在C++和Java中都是现成提供的。所以很简单，直接给代码。
C++:
#include <bits/stdc++.h>
using namespace std;
map<int,int> vis;
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
vis.clear();
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
int a;
scanf("%d", &a);
vis[a]++;
}
printf("%d\n", vis.size());
for(map<int,int>::iterator it = vis.begin(); it != vis.end(); it++) printf("%d %d\n", it->first,it->second);
}
return 0;
}
Java:
import java.io.*;
import java.util.*;
public class Main
{
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String args[]) throws Exception
{
HashMap<Integer,Integer> vis = new HashMap<Integer,Integer>();//或者使用TreeMap
int t = Integer.parseInt(in.readLine());
for(int c = 0; c < t; c++)
{
vis.clear();
int n = Integer.parseInt(in.readLine());
for(int i = 0; i < n; i++)
{
int a = Integer.parseInt(in.readLine());
Object tmp = vis.get(a);
if(tmp == null) tmp = 0;
vis.put(a,((Integer)tmp)+1);
}
out.write(Integer.toString(vis.size()));
out.newLine();
Iterator<Map.Entry<Integer,Integer>> it = vis.entrySet().iterator();
while (it.hasNext()){
Map.Entry<Integer,Integer> entry = it.next();
out.write(Integer.toString(entry.getKey())+" "+Integer.toString(entry.getValue()));
out.newLine();
}
}
out.flush();
}
}
【F题】
模拟题，稍微有点烦，看懂了就很好写了。
C++:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3000+10;
int p[2],w[2],c[MAXN],d[MAXN],s[MAXN];
//p两个人的现金,w两个人额位置,c和d表示每块地的标价和过路费,s表示每块地的购买状态-1没人买0-A买了1-B买了
void buy(int id)
{
if(-1 == s[w[id]])
{
if(p[id] >= c[w[id]])
p[id] -= c[w[id]],s[w[id]] = id;
}
else if(id != s[w[id]])
{
p[id] -= d[w[id]];
p[id^1] += d[w[id]];
}
}
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
int n,m;
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++) scanf("%d %d", &c[i], &d[i]);
p[0] = p[1] = 10000;
w[0] = w[1] = 0;
memset(s,-1,sizeof(s));
while(m--)
{
int a,b;
scanf("%d%d",&a, &b);
w[0] = (w[0]+a)%n;
w[1] = (w[1]+b)%n;
buy(0);buy(1);
}
printf("%d %d\n", p[0],p[1]);
}
return 0;
}
Java:
import java.io.*;
import java.util.*;
public class Main
{
final static int MAXN = 3000+10;
static int p[] = new int[2],w[] = new int[2],c[] = new int[MAXN],d[] = new int[MAXN],s[] = new int[MAXN];
//p两个人的现金,w两个人额位置,c和d表示每块地的标价和过路费,s表示每块地的购买状态-1没人买0-A买了1-B买了
public static void buy(int id)
{
if(-1 == s[w[id]])
{
if(p[id] >= c[w[id]])
{
p[id] -= c[w[id]];
s[w[id]] = id;
}
}
else if(id != s[w[id]])
{
p[id] -= d[w[id]];
p[id^1] += d[w[id]];
}
}
public static void main(String args[]) throws Exception
{
Scanner cin=new Scanner(System.in);
int t = cin.nextInt();
while(t-- > 0)
{
int n = cin.nextInt(),m = cin.nextInt();
for(int i = 0; i < n; i++)
{
c[i] = cin.nextInt();
d[i] = cin.nextInt();
}
p[0] = p[1] = 10000;
w[0] = w[1] = 0;
for(int i = 0; i < n; i++) s[i] = -1;
while(m-- > 0)
{
int a = cin.nextInt(),b = cin.nextInt();
w[0] = (w[0]+a)%n;
w[1] = (w[1]+b)%n;
buy(0);buy(1);
}
System.out.printf("%d %d\n", p[0],p[1]);
}
}
}
【G题】
首先，把这段代码复制进去毫无疑问是超时的(不然还出什么题)。
仔细一想，求的不就是对于每个a[i]找出0~i-1中的最小值mi，然后对每个a[i]-mi求最大值就可以。而这个最小值只需要在从0->n-1找的时候顺便维护下就可以了。复杂度O(n)。
C++:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000+10;
int a[MAXN];
int get_max(int len)
{
int ans = a[1]-a[0],mi = a[0];
for(int i = 1; i < len; i++)
{
ans = max(ans,a[i]-mi);
mi = min(mi,a[i]);
}
return ans;
}
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
printf("%d\n", get_max(n));
}
return 0;
}
Java:
import java.io.*;
import java.util.*;
public class Main
{
final static int MAXN = 100000+10;
static int a[] = new int[MAXN];
public static int get_max(int len)
{
int ans = a[1]-a[0],mi = a[0];
for(int i = 1; i < len; i++)
{
if(ans < a[i]-mi) ans = a[i]-mi;
if(mi > a[i]) mi = a[i];
}
return ans;
}
public static void main(String args[]) throws Exception
{
Scanner cin=new Scanner(System.in);
int t = cin.nextInt();
while(t-- > 0)
{
int n = cin.nextInt();
for(int i = 0; i < n; i++) a[i] = cin.nextInt();
System.out.printf("%d\n", get_max(n));
}
}
}
本题考察的是你会不会使用循环语句(嗯，就这样，简单吧。)
