Google CodeJam Round1A没赶上做，刚好有场SRM，然后就打了
当场只做了T1…T2没调完…
果然老年人…
好久没做Topcoder格式都快忘了，扒了Leanote的模板
ps.掉rating了..
T1
Description
$n$个数字，$n+1$个位置，用每次移动一步，排成正确顺序。
$n\leqslant 500$
Solution
这其实就是找环就完了，随便把一个放在最后，然后一个个移动就好了…
其实这是个排列，当时读题的时候没看到…然后想复杂了许多，所以代码有点长…
Code1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
using namespace std;
typedef long long LL;
const int N = 100050;
const int M = 205;
const LL p = 1000000007;
const int oo = 0x3fffffff;
const LL OO = 1e18;
LL Pow(LL a,LL b,LL r=1) { for(;b;b>>=1,a=a*a%p) if(b&1) r=r*a%p;return r; }
inline LL in(LL x=0,char ch=getchar(),int v=1) {
while(ch>'9' || ch<'0') v=ch=='-'?-1:v,ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return x*v;
}
/*end*/
class CS {
private:
int n;
vector<int> a, ans;
map<int, int> rk, rrk, wz;
int find() {
for(int i=0; i<n; i++) if(rk[a[i]]!=i) return i;
return -1;
}
void addAns(int x) {
ans.push_back(x);
}
void Sol(int x) {
int fx=a[x];
addAns(x);
for(;;) {
addAns(wz[rrk[x]]);
a[x]=rrk[x];
x=wz[rrk[x]];
if(rrk[x]==fx) break;
}
a[x]=fx;
addAns(n);
}
public:
vector<int> FC(vector<int> target) {
a=target;
sort(a.begin(), a.end());
n=a.size();
for(int i=0; i<n; i++) {
rk[a[i]]=i;
rrk[i]=a[i];
wz[target[i]]=i;
// cout << a[i] << " " << i << endl;
}
a=target;
for(int x=find();~x;x=find()) {
Sol(x);
// cout << x << endl;
}
return ans;
}
};
int main() {
ios::sync_with_stdio(false);
// if(freopen("in.in","r",stdin));
CS py;
LL n;
vector<int> a, ans;
cin>>n;
for(int i=1; i<=n; i++) {
int x;
cin >> x;
a.push_back(x);
}
ans=py.FC(a);
for(int i=0; i<ans.size(); i++) cout<< ans[i]<<" ";
return 0;
}
/*
*/
T2
Description
一个人拿着刷子刷路，给出要刷的路段，和每次最长能刷的距离，求最短路程
$n\leqslant 500, dStart[i] < dEnd[i] < 2\times 10^9$
Solution
这题倒着贪心，当时想出来了，有个地方写的有问题。
贪心为啥对呢…因为如果刷一次的话，最远路程便是最后一个，如果你还刷了前面的部分，那么第二次刷的路程就会变大。(没怎么想证明…对就vans了)
Code1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
using namespace std;
typedef long long LL;
const int N = 550;
const int M = 205;
const LL p = 1000000007;
const int oo = 0x3fffffff;
const LL OO = 1e18;
LL Pow(LL a,LL b,LL r=1) { for(;b;b>>=1,a=a*a%p) if(b&1) r=r*a%p;return r; }
inline LL in(LL x=0,char ch=getchar(),int v=1) {
while(ch>'9' || ch<'0') v=ch=='-'?-1:v,ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return x*v;
}
/*end*/
class CS {
private:
int n, m;
LL ans;
vector<int> a;
LL calc(int x, int t) {
return ((LL)x+x-(LL)(t-1)*m)*t;
}
public:
LL FC(vector <int> dStart, vector <int> dEnd, int paintPerBrush) {
n=dStart.size();
ans=0;
m=paintPerBrush;
// for(int i=0; i<n;i++) cout<< dStart[i] << " " << dEnd[i]<<endl;
// cout << m << endl;
for(int i=0; i<n; i++) a.push_back(dEnd[i]-dStart[i]);
for(int i=n-1;i>=0;--i) {
int t=a[i]/m;
ans+=calc(dStart[i]+a[i], t);
// cout << calc(dStart[i]+a[i], t) << endl;
a[i]=a[i]%m;
t=m;
if(a[i]==0) continue;
ans+=2LL*(dStart[i]+a[i]);
// cout << 2LL*(dStart[i]+a[i]) << endl;
for(;t>0 && i>=0; i--) {
if(a[i]<=t) {
t-=a[i], a[i]=0;
} else {
a[i]-=t, t=0, i++;
break;
}
}
// debug(i),debug(ans);
}
return ans;
}
};
int main() {
ios::sync_with_stdio(false);
// if(freopen("in.in","r",stdin));
CS py;
int n, m, x;
cin >> n;
vector<int> a,b;
for(int i=1;i<=n; i++) {
cin >> x;
a.push_back(x);
}
for(int i=1;i<=n; i++) {
cin >> x;
b.push_back(x);
}
cin >> m;
cout << py.FC(a, b, m) << endl;
return 0;
}
/*
3 1 10 20 4 13 22 2
*/
