站长统计代码,网站设计大小,html转wordpress教程,新手跨境电商怎么做Problem - 1481C - Codeforces 思路#xff1a;逆序考虑#xff0c;因为每一块木板都是被最后一次粉刷所决定的。
从后往前开始#xff0c;对于 c i c_i ci来说#xff0c;
如果这个颜色还有没有涂的木板#xff0c;那么涂到其中一个木板即可如果这个颜色下没有未涂的…Problem - 1481C - Codeforces 思路逆序考虑因为每一块木板都是被最后一次粉刷所决定的。
从后往前开始对于 c i c_i ci来说
如果这个颜色还有没有涂的木板那么涂到其中一个木板即可如果这个颜色下没有未涂的木板找到一个已经土过的木板如果这个颜色没有被涂且没有已经被涂的木板那么涂到一个相同木板上如果这个颜色没有被涂却没有已经被涂的木板同时也没有相同木板那么无解。
最后再检验一下是否可行即可。
代码如下
void solve() {int n,m; cinnm;bool ok true;int pos -1;vectorint a(n 1), b(a), c(m 1),ans(m 1), e(n 1, -1);/*** ans存第j个人涂哪个木板* e存第z个颜色的最远位置*/vectorvectorint g(n 1);for(int i 1 ; i n; i) cina[i];for(int i 1; i n; i) cinb[i];for(int i 1; i m; i) cinc[i];for(int i 1; i n; i) {// 不相同表示需要更改先进行标记if(a[i] ! b[i]) g[b[i]].push_back(i);e[b[i]] i;}for(int i m; i 1; --i) {// 现在木板中没有将木板颜色更改为ci的需求if(g[c[i]].size() 0) {// 如果是-1表示没有已经被涂色的if(pos -1) {// 如果这个ci颜色在木板中不存在结束if(e[c[i]] -1) {ok false;break;}// 否则涂到相同木板上pos e[c[i]];}} else {// 位置更新pos g[c[i]].back();g[c[i]].pop_back();a[pos] b[pos];}// 第i个人要涂的位置ans[i] pos;}// 检查一下是否符合for(int i 1; i n; i) ok a[i] b[i];if(ok) {coutYES\n;for(int i 1; i m; i) coutans[i] \n[i m];} else coutNO\n;
}CF1481C Fence Painting - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
