這是我第一次參加了這次CSP考試，300分，寫(xiě)了124三題，模擬題到現(xiàn)在都沒(méi)看過(guò)題面沒(méi)看，笑，t4寫(xiě)成模擬加數(shù)據(jù)結(jié)構(gòu)，200+行，因?yàn)橐粋€(gè)小錯(cuò)誤調(diào)了1h，錯(cuò)失了大好機(jī)會(huì)?？荚嚟h(huán)境的VSC配置的字體太小，甚至連空格都看不清有還是沒(méi)有，當(dāng)時(shí)沒(méi)想到可以重新配置，這可能也是我t4調(diào)了1h的原因。
距離下一次CSP考試考試還有20天左右，特此回顧。代碼均為考試時(shí)提交的代碼，補(bǔ)充思路。
數(shù)據(jù)歸一化處理，根據(jù)給定公式進(jìn)行計(jì)算。
這里要求了輸出精度，通過(guò)流的格式標(biāo)志值
i
o
s
_
b
a
s
e
:
:
f
i
x
e
d
ios\_base::fixed
ios_base::fixed和
s
e
t
p
r
e
c
i
s
i
o
n
(
)
setprecision()
setprecision()設(shè)置輸出小數(shù)點(diǎn)后10位。
重慶分公司
重慶分公司
cout<< fixed<< setprecision(10)<< (a[i] - av) / sD<< '\n';void solve() {int n; cin >>n;
vectora(n);
double sum = 0;
for (int i = 0; i< n; i++) cin >>a[i], sum += a[i];
double av = sum / n;
double sD = 0;
for (int i = 0; i< n; i++) {sD += (a[i] - av) * (a[i] - av);
}
sD /= n;
sD = sqrt(sD);
for (int i = 0; i< n; i++) {cout<< fixed<< setprecision(10)<< (a[i] - av) / sD<< '\n';
}
} 
給定一個(gè)大矩陣
L
L
L和小矩陣
S
S
S，均為01矩陣，問(wèn)
L
L
L有多少處和
S
S
S匹配（
L
L
L有多少個(gè)子矩陣和
S
S
S相等）。
暴力匹配，時(shí)間為
O
(
L
2
S
2
)
O(L^2S^2)
O(L2S2)，雖然一旦不匹配就可以終止，但樂(lè)觀估計(jì)不優(yōu)于
O
(
L
2
)
O(L^2)
O(L2).
因此，需要采取一些方法，注意到
n
≤
1000
n\leq 1000
n≤1000，即‘1’的個(gè)數(shù)不超過(guò)1000，而且
因此從大矩陣‘1’的位置開(kāi)始匹配，理論復(fù)雜度為
O
(
n
×
S
2
)
O(n\times S^2)
O(n×S2)，約為
2.5
e
6
2.5e6
2.5e6，時(shí)間上可以過(guò)，但是還有空間的問(wèn)題，無(wú)法開(kāi)
1
e
18
1e18
1e18的
b
o
o
l
bool
bool數(shù)組，因此用
s
e
t
<
p
a
i
r
<
i
n
t
,
i
n
t
>
>
set
set>Set;
vector>a, b;
void solve() {int n, L, S;
cin >>n >>L >>S;
int x, y;
for (int i = 1; i<= n; i++) {cin >>x >>y;
Set.insert({x, y});
}
int m;
for (int i = 0; i<= S; i++) {for (int j = 0; j<= S; j++) {cin >>m;
if (m) {a.push_back({S - i, j}); // a tree
}
else b.push_back({S - i, j});
}
}
int ans = 0;
for (auto i : Set) {if (i.first + S >L || i.second + S >L) continue;
bool ok = 1;
// cout<< "i: "<< i.first<< ' '<< i.second<< '\n';
for (auto j : a) {// cout<< "j: "<< j.first<< ' '<< j.second<< '\n';
int tx = i.first + j.first;
int ty = i.second + j.second;
// cout<< tx<< ' '<< ty<< '\n';
if (Set.find({tx, ty}) == Set.end()) {ok = 0;
break;
}
}
for (auto j : b) {if (!ok) break;
int tx = i.first + j.first;
int ty = i.second + j.second;
// cout<< tx<< ' '<< ty<< '\n';
if (Set.find({tx, ty}) != Set.end()) {ok = 0;
break;
}
}
if (ok) ans++;
}
cout<< ans<< '\n';
} 原來(lái)這題是圖形學(xué)的背景，這學(xué)期剛剛在學(xué)CG，確實(shí)CG中很多用數(shù)據(jù)結(jié)構(gòu)優(yōu)化（比如多邊形填充的APT）的算法。
限制了光線只能水平或者豎直地射，包括反射后的光線，而反射面的端點(diǎn)坐標(biāo)均為整數(shù)，光源也設(shè)置在整點(diǎn)位置，因此可以認(rèn)為光線在網(wǎng)格格線上運(yùn)動(dòng)，更進(jìn)一步，可以認(rèn)為反射面只設(shè)定在格點(diǎn)上。
光線在反射過(guò)程中存在耗散。
1，2定義了反射面的增刪操作，3設(shè)置光源詢問(wèn)
t
t
t時(shí)間后，光線的位置
(
x
,
y
)
(x,y)
(x,y)，以及剩余光線強(qiáng)度
I
I
I。
這個(gè)
3
e
5
3e5
3e5的保證意味著可以
O
(
n
)
O(n)
O(n)地將反射面的性質(zhì)（耗散率，放置方向）存儲(chǔ)（或者移除）到一定區(qū)間的格點(diǎn)中，用格點(diǎn)代表反射面，格點(diǎn)數(shù)就是
∑
∣
x
1
?
x
2
∣
\sum|x_1-x_2|
∑∣x1??x2?∣.
網(wǎng)格大小為
1
e
9
2
1e9^2
1e92，因此必須不能
O
(
t
)
O(t)
O(t)模擬光線的運(yùn)動(dòng)。光線的運(yùn)動(dòng)狀態(tài)通過(guò)當(dāng)前位置
(
x
,
y
)
(x,y)
(x,y)和方向
d
d
d，如果
d
d
d不變，可以
O
(
1
)
O(1)
O(1)確定
t
t
t時(shí)間后的位置，而
d
d
d變化由反射引起，反射是由于經(jīng)過(guò)了反射面，即具有反射性質(zhì)的格點(diǎn)（下稱為格點(diǎn)）。
結(jié)合代碼講講：
定義了結(jié)構(gòu)體
m
i
r
r
o
r
mirror
mirror，解決題目規(guī)定的對(duì)反射面整體的增加和刪除操作，對(duì)應(yīng)結(jié)構(gòu)體方法
i
n
i
t
init
init和
c
l
r
clr
clr，而
r
e
s
e
t
reset
reset是將反射性質(zhì)賦予區(qū)域中的格點(diǎn)，就是將該點(diǎn)存儲(chǔ)于
m
a
p
<
l
l
,
s
e
t
<
l
l
>
>
map
if (setX[x].size() == 0) setX.erase(x);w o r k work work函數(shù)模擬光線的運(yùn)動(dòng)，是遞歸函數(shù)，輸入?yún)?shù) x , y x,y x,y是當(dāng)前坐標(biāo)， d d d是方向， I I I是強(qiáng)度， t t t是詢問(wèn) t t t時(shí)刻后的位置。
void work(ll x, ll y, int d, double I, ll t) {這個(gè)函數(shù)我按照運(yùn)動(dòng)方向分為了4個(gè)部分寫(xiě)，因?yàn)槊總€(gè)方向上
s
e
t
set
set調(diào)用的二分方法不同，
u
p
p
e
r
_
b
o
u
n
d
upper\_bound
upper_bound或者
l
o
w
e
r
_
b
o
u
n
d
lower\_bound
lower_bound，而且邊界情況也不好統(tǒng)一表達(dá)，只能
i
f
e
l
s
e
ifelse
ifelse分類討論了。
具體看一種情況，光線沿著
x
x
x軸增加：
此時(shí)
y
y
y不變，首先判斷該格線上是否有反射點(diǎn)，沒(méi)有訪問(wèn)會(huì)RE：
if (setY.find(y) == setY.end()) {若沒(méi)有，則一直前進(jìn)；否則，則調(diào)用 s e t set set自帶的二分方法：
auto it = setY[y].upper_bound(x); // 找到第一個(gè)大于x的數(shù)若沒(méi)有找到這樣的反射點(diǎn)，則一直前進(jìn)；否則可能發(fā)生發(fā)射，還要檢查到達(dá)該點(diǎn)的用時(shí)，時(shí)間充足發(fā)生反射，寫(xiě)到這里大家肯定發(fā)現(xiàn)這是道具有大模擬性質(zhì)的t4了。
發(fā)生反射，由于光線原來(lái)方向沿
x
x
x增加，只可能變?yōu)檠?
y
y
y方向增加或者減少，這個(gè)通過(guò)鏡子的放置方向確定，遞歸。
const int N = 1e5 + 5;
const int maxn = 1e5 + 5;
// setsetX[2 * N];
// setsetY[2 * N];
map>setX;
map>setY;
map, int>mp;
struct mirror
{void init(int ID, ll a1, ll b1, ll a2, ll b2, double A) {id = ID;
x1 = a1; y1 = b1; x2 = a2; y2 = b2; a = A;
}
void reset() {if (x1 >x2) dx = -1;
else dx = 1;
if (y1 >y2) dy = -1;
else dy = 1;
ll x = x1 + dx, y = y1 + dy;
while (x != x2) {setX[x].insert(y);
setY[y].insert(x);
mp[{x, y}] = id; // 將點(diǎn)對(duì)應(yīng)至鏡子
x += dx; y += dy;
}
}
void clr() {ll x = x1 + dx, y = y1 + dy;
while (x != x2) {setX[x].erase(y);
setY[y].erase(x);
if (setX[x].size() == 0) setX.erase(x);
if (setY[y].size() == 0) setY.erase(y);
mp.erase({x, y});
x += dx; y += dy;
}
}
int id;
ll x1, y1, x2, y2;
int dx, dy;
double a;
} M[maxn];
void work(ll x, ll y, int d, double I, ll t) {// cout<< "work: "<< x<< ' '<< y<< ' '<< d<< ' '<< I<< ' '<< t<< '\n';
if (I< 1.0) {// 已經(jīng)完全耗散
cout<< "0 0 0\n";
return;
}
// if (x< 0 || y< 0) return;
if (d == 0) {// x ->沿著x軸增加
if (setY.find(y) == setY.end()) {cout<< x + t<< ' '<< y<< ' '<< (int)I<< '\n';
return;
}
auto it = setY[y].upper_bound(x); // 找到第一個(gè)大于x的數(shù)
if (it == setY[y].end()) {// 若無(wú)則代表沒(méi)有鏡子
cout<< x + t<< ' '<< y<< ' '<< (int)I<< '\n';
return;
}
else {ll nx = *it;
if (t< nx - x) {// 看剩余時(shí)間是否充足
cout<< x + t<< ' '<< y<< ' '<< (int)I<< '\n';
return;
}
int mir = mp[{nx, y}]; // 進(jìn)行一次反射
auto Mir = M[mir];
if (Mir.dx * Mir.dy >0) {// 判斷鏡子方向
work(nx, y, 1, I * Mir.a, t - (nx - x));
}
else {work(nx, y, 3, I * Mir.a, t - (nx - x));
}
}
}
else if (d == 1) {// y ^
if (setX.find(x) == setX.end()) {cout<< x<< ' '<< y + t<< ' '<< (int)I<< '\n';
return;
}
auto it = setX[x].upper_bound(y);
if (it == setX[x].end()) {cout<< x<< ' '<< y + t<< ' '<< (int)I<< '\n';
return;
}
else {ll ny = *it;
if (t< ny - y) {cout<< x<< ' '<< y + t<< ' '<< (int)I<< '\n';
return;
}
int mir = mp[{x, ny}];
auto Mir = M[mir];
if (Mir.dx * Mir.dy >0) {work(x, ny, 0, I * Mir.a, t - (ny - y));
}
else {work(x, ny, 2, I * Mir.a, t - (ny - y));
}
}
}
else if (d == 2) {// x<- 沿著x軸減少
if (setY.find(y) == setY.end()) {cout<< x - t<< ' '<< y<< ' '<< (int)I<< '\n';
return;
}
auto it = setY[y].lower_bound(x);
if (it == setY[y].begin()) {// 沒(méi)有小于x的數(shù)
cout<< x - t<< ' '<< y<< ' '<< (int)I<< '\n';
return;
}
else {it--; // 第一個(gè)小于x的數(shù)
ll nx = *it;
if (t< x - nx) {cout<< x - t<< ' '<< y<< ' '<< (int)I<< '\n';
return;
}
int mir = mp[{nx, y}];
auto Mir = M[mir];
if (Mir.dx * Mir.dy >0) {work(nx, y, 3, I * Mir.a, t - (x - nx));
}
else {work(nx, y, 1, I * Mir.a, t - (x - nx));
}
}
}
else if (d == 3) {// y v
if (setX.find(x) == setX.end()) {cout<< x<< ' '<< y - t<< ' '<< (int)I<< '\n';
return;
}
auto it = setX[x].lower_bound(y);
if (it == setX[x].begin()) {cout<< x<< ' '<< y - t<< ' '<< (int)I<< '\n';
return;
}
else {it--;
ll ny = *it;
if (t< y - ny) {cout<< x<< ' '<< y - t<< ' '<< (int)I<< '\n';
return;
}
int mir = mp[{x, ny}];
auto Mir = M[mir];
if (Mir.dx * Mir.dy >0) {work(x, ny, 2, I * Mir.a, t - (y - ny));
}
else {work(x, ny, 0, I * Mir.a, t - (y - ny));
}
}
}
}
void solve() {int m; cin >>m;
ll op, x1, y1, x2, y2, d, t, k;
double a, I;
for (int i = 1; i<= m; i++) {cin >>op;
if (op == 1) {cin >>x1 >>y1 >>x2 >>y2 >>a;
M[i].init(i, x1, y1, x2, y2, a); // 添加反射鏡
M[i].reset();
}
else if (op == 2) {cin >>k;
M[k].clr();
}
else if (op == 3) {cin >>x1 >>y1 >>d >>I >>t;
if (t == 0) {cout<< x1<< ' '<< y1<< ' '<< (int)I<< '\n';
}
work(x1, y1, d, I, t);
}
}
} 你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
