当前位置：首页 > news >正文

SMU Summer 2024 Contest Round 2

news 来源：原创 2024/9/20 7:57:36

[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;
}