ZOJ 4082 Little Sub and his Geometry Problem题解
题意
f(u,v)：x小于等于u且y小于等于v的点才对f有贡献，每个这样的点贡献(u-x)+()
思路
且等号当且仅当
因此对于输入的
当我们固定一个变量的时候，
因此，我选择横竖两条线移动。
初始状态u=0,v=N.此时f值显然过小。
对于一个状态，
如果f过小，则只能往竖线右调，f才可能增大。
如果f过大，则只能横线往下调。
如果f刚好，答案计数加1，同时，这个u已经不可能有v符合了。往右调（其实往下调也行，关键是要固定一种走法）。
f过小时，v往上调是没有意义的，因为初始状态是v所能取的最大值（N），能到达目前的状态，是从前面的太大或者已经计数过的答案状态转移过来的。往上调就是是走回头路，回去要不就是f过大，要不就是已经计数了的恰好等于f的状态。
同理,f过大时，竖线左调是没有意义的。
同时根据（标号①）的结论易证，不会有情况疏漏掉。
换句话说，如此移动，不重不漏，至多移动2N次。
具体可以参考C++源码
注意，getCount不要用二分，直接枚举就好了。
二分反而会更慢，慢原因是二分需要先排序，排序是
而注意到getCount(u,v)每一个u至多查询1次，直接枚举是
复杂度估计，由于每个片段至多查询一次，且最坏情况下所有片段都查询了。因此对于一个输入C，总的复杂度是
有个2倍是因为对反过来的rp也要考虑。
因此总复杂度是
不考虑系数，大概带入数字算一下。不超过20*10*10^5+(1000-20)*10*10^4=1.18*10^8.
4s时间限制是OK的。
源码
java（Tle）
java一开始我的java jdk时1.8.ZOJ评测时1.7.莫名RE
后来用1.7，还是莫名RE.
最后故意加死循环，提交。二分测试发现ZOJ Java switch不支持枚举型变量。黑人问号。
最后无奈改成if语句，然后从Re变成Tle了。根据网上的进行了输入输出优化还是不行。
import java.util.*;
import java.io.*;
public class Main {
static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) {
try {
cin.nextToken();
int cnt = (int) cin.nval;
LittleSubAndHisGeometryProblem p;
for (int i = 0;i < cnt; ++i) {
p = new LittleSubAndHisGeometryProblem();
p.run();
}
cout.flush();
} catch (Exception e) {
}
}
}
class LittleSubAndHisGeometryProblem{
final int N;
int pointCnt;
PointsSys normal;
PointsSys reverse;
int queryCnt;
LittleSubAndHisGeometryProblem() throws Exception {
Main.cin.nextToken();
N = (int)Main.cin.nval;
Main.cin.nextToken();
pointCnt = (int)Main.cin.nval;
// 做准备工作，方便满足“a=a0,b<=b0的点的个数及他们的b之和”
normal = new PointsSys();
reverse = new PointsSys();
int x,y;
for (int i = 0;i < pointCnt; ++i) {
Main.cin.nextToken();
x = (int)Main.cin.nval;
Main.cin.nextToken();
y = (int)Main.cin.nval;
normal.add(x,y);
reverse.add(y,x);
}
Main.cin.nextToken();
queryCnt = (int)Main.cin.nval;
}
class PointSysQueryInfo{
int cnt = 0;
long sum = 0;
void add(long a) {
++cnt;
sum += a;
}
}
class PointsSys{
int cnt;
ArrayList<ArrayList<Integer>> p;
PointsSys() {
p = new ArrayList<ArrayList<Integer>>();
for (int i = 0;i <= N; ++i)
p.add(new ArrayList<Integer>());
}
void add(int x,int y) {
p.get(x).add(y);
}
void query(int x,int y,PointSysQueryInfo change) {
// 返回X值恰好为x,且Y值小于等于y的所有点的信息
// 返回点数和sigama(y-Yi) Yi取遍所有的满足要求的点的Y
change.cnt = 0;
change.sum = 0;
ArrayList<Integer> list = p.get(x);
for (int Y : list)
if (Y <= y)
change.add(y-Y);
}
}
public enum Move{
Right,Down
}
void count() {
// 求解符合题意的方案数
queryAns = 0;
if (2L*N*pointCnt <= c)
return;
int u = 0;
int v = N;
PointSysQueryInfo curr = new PointSysQueryInfo();
PointSysQueryInfo change = new PointSysQueryInfo();
Move moveFlag = Move.Right;
//boolean first = true;
while (u <= N && v > 0) {
if (curr.sum == c)
++queryAns;
if (moveFlag == Move.Right) { // Go Right
++u;
if (u > N) return;
normal.query(u, v ,change);
curr.sum += change.sum + curr.cnt;
curr.cnt += change.cnt;
} else { // Go Down
if (v <= 0) return;
reverse.query(v,u,change);
--v;
curr.cnt -= change.cnt;
curr.sum -= change.sum+curr.cnt;
}
if (curr.sum >= c)
moveFlag = Move.Down;
else
moveFlag = Move.Right;
}
return;
}
long c;
int queryAns;
void run() throws Exception {
boolean first = true;
for (int i = 0; i < queryCnt; ++i) {
Main.cin.nextToken();
c = (long)Main.cin.nval;
count();
if (first) {
Main.cout.print(queryAns);
first = false;
} else {
Main.cout.print(" "+queryAns);
}
}
Main.cout.println();
}
}
C++ （AC）
#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 100005;
int N,K;
vector<int>p[kMaxN];
vector<int>rp[kMaxN];
void getCount(vector<int>&p,int b,int &cnt,long long &s) {
cnt = 0;
s = 0;
for (auto y : p)
if (y <= b) {
++cnt;
s += b-y;
}
}
int count(long long c) {
if (c >= 2ll*(long long)N*(long long)K)
return 0;
int u = 0;
int v = N;
int ans = 0;
bool isGoRight = true;
long long f,f0;
int cnt,cnt0;
f = 0; cnt = 0;
while (u <= N && v >= 1) {
if (f == c)
++ans;
if (isGoRight) { // Go Right
++u;
getCount(p[u],v,cnt0,f0);
f += f0+(long long)cnt;
cnt += cnt0;
} else { // Go Down
getCount(rp[v],u,cnt0,f0);
--v;
cnt -= cnt0;
f -= f0+(long long)cnt;
}
isGoRight = f < c;
}
return ans;
}
void work() {
cin>>N>>K;
for (int i = 0; i <= N; ++i) {
p[i].clear();
rp[i].clear();
}
int x,y;
for (int i = 0;i < K; ++i) {
cin>>x>>y;
p[x].push_back(y);
rp[y].push_back(x);
}
int Q;
cin>>Q;
long long c;
int ans;
for (int i = 0; i < Q; ++i) {
cin>>c;
ans = count(c);
if (i)
cout<<' '<<ans;
else
cout<<ans;
}
cout<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while (T--)
work();
return 0;
}
