[ABC357C] Sierpinski carpet - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)

思路:通過因為圖形的生成過程是完全一樣的。可以通過遞歸，不斷分形。函數process(x,y,k)定義為以坐標(x,y)為左上角,填充sqrt3(k)級的地毯。

int n;
int c[800][800];        默認全為0,  0對應'.'  1對應'#'
void process(int x,int y,int k){      填充左上角為x,y的sqrt3(k)級地毯if(k==0) {c[x][y]=1;  base casereturn;}int t=k/3;process(x,y,t);process(x,y+t,t);process(x,y+t*2,t);process(x+t,y,t);//process(x+t,y+t,t);  留白process(x+t,y+t*2,t);process(x+t*2,y,t);process(x+t*2,y+t,t);process(x+t*2,y+t*2,t);
}
[ABC357C] Sierpinski carpet
https://www.luogu.com.cn/problem/AT_abc357_c
void solve(){           補A--遞歸 分型  "好題"  要清楚是怎么'跳躍',分型的,bask case是什么cin>>n;int t=pow(3,n);process(1,1,t);for(int i=1;i<=t;i++){for(int j=1;j<=t;j++){if(c[i][j]) cout<<"#";else cout<<".";}cout<<endl;}
}

//    ######### ######### #########
//    #.##.##.# #.##.##.# #.##.##.#
//    ######### ######### #########
//    ###...### ###...### ###...###
//    #.#...#.# #.#...#.# #.#...#.#
//    ###...### ###...### ###...###
//    ######### ######### #########
//    #.##.##.# #.##.##.# #.##.##.#
//    ######### ######### #########
//
//    ######### ......... #########
//    #.##.##.# ......... #.##.##.#
//    ######### ......... #########
//    ###...### ......... ###...###
//    #.#...#.# ......... #.#...#.#
//    ###...### ......... ###...###
//    ######### ......... #########
//    #.##.##.# ......... #.##.##.#
//    ######### ......... #########
//
//    ######### ######### #########
//    #.##.##.# #.##.##.# #.##.##.#
//    ######### ######### #########
//    ###...### ###...### ###...###
//    #.#...#.# #.#...#.# #.#...#.#
//    ###...### ###...### ###...###
//    ######### ######### #########
//    #.##.##.# #.##.##.# #.##.##.#
//    ######### ######### #########

[ABC325D] Printing Machine - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)

思路:寫的有點迷糊的貪心題。顯而易見的是，在L相同的情況下，肯定是先選擇R更小的。

所以可以把輸入按照L從小到大排列，依次處理，L相同的 按L+R從小到大排列。之后怎么處理呢?

一秒一秒枚舉時間是不可能的。但是可以知道的是，中間有很多間隔是沒意義的。

那么可以從time=1開始，把開始時間L與當前時間一樣的的物品的右區間放入優先隊列中。之后一個一個取。直到隊列為空。要注意的是！當且僅當隊列為空時，才判斷time跳躍到下一個區間的開始時間L。不然的話可能優先隊列里面還有物品，并且時間大于time。仍然可以取,但是因為提前跳躍了，導致沒取到。

int n;
pair<int,int> arr[200005];
//multiset<pair<int,int>> mst;
畫個時間區間軸。
[ABC325D] Printing Machine
https://www.luogu.com.cn/problem/AT_abc325_d
void solve(){               補D--貪心 "好題"  太頭疼了這個題。。cin>>n;for(int i=1;i<=n;i++) {cin>>arr[i].first>>arr[i].second;arr[i].second=arr[i].first+arr[i].second;}sort(arr+1,arr+n+1);     按l從小到大排序，l相等的話，按l+r從小到大排序.priority_queue<int,vector<int>,greater<int>> pq;int ans=0,idx=1,time=1;while(idx<=n||pq.size()){//if(arr[idx].first!=time&&idx<=n) time=arr[idx].first;   這個代碼會導致直接跳過很多if(pq.size()==0&&idx<=n) time=arr[idx].first;while(idx<=n&&arr[idx].first==time) {pq.emplace(arr[idx++].second);}while(pq.size()&&pq.top()<time) pq.pop();if(pq.size()) ans++,pq.pop();time++;}cout<<ans;
}
//的確是貪心，但是策略不對
//優先選晚結束或者早結束的貪心策略都不對:hack:
//expect:4   answer:3
//key:這個樣例的問題是怎么處理在第三秒時候的選擇.也是這題的關鍵.
5
1 3 [1,4] 1s
1 3 [1,4] 2s
1 3 [1,4] 3s
2 1 [2,3]
2 1 [2,3]

?[ABC299E] Nearest Black Vertex - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)

?思路:這個題不難出思路，也不難實現。注意細節即可。

o(k*n)預處理出每個pi滿足約束時需要成為黑點的候選點mayBlack[pi]。同時記錄不可能成為黑點的點notBlack.即在di范圍內的點。

最后遍歷每一個候選點的mayBlack[pi]，排除不可能的點。如果某一個mayBlack[pi]里的點都是不可能的點notBlack，那么No，否則Yes.

yes的時候直接把所有非notBlack的點涂黑即可。

int n,m,k;
vector<int> vct[2005];
vector<int> mark,mayBlack[2005];
unordered_map<int,bool> notBlack;
思路:--AC
o(k*n)預處理出每個pi需要成為黑點的候選點。同時記錄不可能成為黑點的點.即在di范圍內的點。
最后遍歷每一個候選點，排除不可能的點。如果某一個mayBlack[pi]里的點都是不可能的點，那么No，否則Yes.
[ABC299E] Nearest Black Vertex  ---全1，不能用01bfs
https://www.luogu.com.cn/problem/AT_abc299_e
void bfs(int s,int d){int dis[2005]={0};queue<int> que;que.emplace(s);while(que.size()){int cur=que.front();que.pop();notBlack[cur]=true;for(auto v:vct[cur]){if(dis[v]!=0||v==s) continue;dis[v]=dis[cur]+1;if(dis[v]!=d) que.emplace(v);else mayBlack[s].emplace_back(v);}}
}
void solve(){       E  至少有一個頂點被涂成黑色。。cin>>n>>m;for(int i=1;i<=m;i++){int u,v; cin>>u>>v;vct[u].emplace_back(v);vct[v].emplace_back(u);}cin>>k;for(int i=1;i<=k;i++){      o(k*n)int p,d; cin>>p>>d;mark.emplace_back(p);if(d==0) mayBlack[p].emplace_back(p);else bfs(p,d);}bool check=true;for(auto mk:mark){                  o(k*n)int cnt=0;for(auto mb:mayBlack[mk]){if(notBlack[mb]) cnt++;}if(cnt==mayBlack[mk].size()) check=false;if(!check) break;}if(check){           notBlack.size()==n也是可以的cout<<"Yes"<<endl;for(int i=1;i<=n;i++) {if(notBlack[i]) cout<<"0";else cout<<"1";}}else cout<<"No"<<endl;
}