好看的静态网站,做公司网站有用吗,合肥房产网新楼盘,ios开发者选项Constructive Problems#xff08;Problem - A - Codeforces#xff09;
题目大意#xff1a;现在有一片城市被摧毁了#xff0c;需要进行重建#xff0c;当一个城市水平相邻和竖直相邻的位置都至少有一个城市的时候#xff0c;该城市可以被重建。所有城市排成n行m列的矩…Constructive ProblemsProblem - A - Codeforces
题目大意现在有一片城市被摧毁了需要进行重建当一个城市水平相邻和竖直相邻的位置都至少有一个城市的时候该城市可以被重建。所有城市排成n行m列的矩形政府先拨款重建一部分城市剩下的需要各个城市自建问政府最少需要重建多少个城市。
思路我们可以发现要想重建城市需要是锯齿形的即 如上图我们可以发现同样是4个但是左图中四个可以伸延至整个区间右图中则一个也不能往外延伸了所以我们可以发现这样斜着的是最优解。那么对于矩形的如下图 所以很容易发现斜着只能补成一个正方形要使整个区域都被覆盖到那么就要取最长的那条边的长度作为个数。
#includebits/stdc.h
using namespace std;
int main()
{int t;scanf(%d,t);while(t--){int n,m;scanf(%d%d,n,m);int ansmax(n,m);printf(%d\n,ans);}
} Begginers ZeldaProblem - B - Codeforces
题目大意给定一棵树我们每次操作可以选择树上的两个点然后将两点及中间的路径合并成一个点。问要将整棵树合并成一个点最少需要操作多少次。
思路这道题怎么说呢挺难受的。我最开始分析样例因为样例给的数据都很简单所以抽出最长路然后剩下的都是直接连在最长路上的点稍微讨论一下就行但是显然这是有bug的 比如上图抽出最长路后剩下的点不是直接连在最长路上的。所以很明显最长路这个思路是不通的然后我竟然又想到每合并一次就去找最长路说人话就是去直接模拟我认为的最优策略。这样的话有两个问题一个是最长路上的各点其实没有那么容易确定我们能确定的就是起点、终点以及路径长度所以合并操作实际并不容易。另外一个是这个会出现超时问题因为我们要找很多次。所以此路不通。然后我又想到能不能从出度的角度来考虑然后我想到的是从出度最大的那些点入手去找规律显然越讨论越复杂它们根本不具有什么规律。至此我想到的路全部不通而且推理验证实际上花的时间远比把这几行思路敲出来要多。最后这道题的思路实际上是从出度最少的点入手我们仔细想想我们的路径当延伸到一个出度大于1的点之后肯定还能再往后延伸直到延伸到一个出度为1的点才停。而且这个是通用的不管我们在什么情况下最优的路径一定要尽可能长未必非要是最长路但它至少是一定不能再延伸了的路。然后将这条路上的点合并成一个之后这两个出度为1的点就消失了。那么实际上我们只需要找到哪些点出度为1然后两两组合如果是奇数个再把不能被组合的那个点加上即可。
#includebits/stdc.h
using namespace std;
int d[100010];
int main()
{int t;scanf(%d,t);while(t--){int n;scanf(%d,n);for(int i1;in;i) d[i]0;for(int i1;in;i){int a,b;scanf(%d%d,a,b);d[a],d[b];}int cnt0;for(int i1;in;i) if(d[i]1) cnt;int ansceil(cnt*1.0/2);printf(%d\n,ans);}
}
Largest SubsequenceProblem - C - Codeforces
题目大意给定一个长为n的字符串s我们能进行的操作就是选定s中字典序最大的子序列然后执行一次向右循环移动一位的操作。问最终能否将s变成非降序排列如果可以输出需要进行的操作次数如果不可以那么就输出-1.
思路我们可以发现对于每个字符串字典序最大的子序列有且仅有一个而且这个序列中的字母是非递增关系。我们对s能进行的更改其实也就是将这个子序列逆转其他的都是改不了的。再进一步将子序列逆转实际上有点类似对称操作因为子序列中第一个字母是最大的最后要将它转到最后一位后面的转到前面来了就不变了所以实际上类似一个对称操作。 所以我们可以在统计最大序列的时候将它们的下标也记录下来然后直接在字符串里进行更改最后判断字符串是否符合要求即可。但是对于第一个字母有多个的情况输出操作数的时候实际是要处理一下的。因为我们正常的就是子序列长度-1但是如下图
我们实际不用转那么多次。所以这个也需要特别统计一下最后的结果应该是子序列长度-1-子序列首字母个数-1对了再多提一句子序列是用类似于栈的思想来统计的。
#includebits/stdc.h
using namespace std;
int main()
{int t;scanf(%d,t);while(t--){int n;scanf(%d,n);string s;cins;vectorchars1;vectorintv;for(int i0;in;i){while(s1.size()s1.back()s[i]){v.pop_back();s1.pop_back();}if(!s1.size()||s1.back()s[i]) s1.push_back(s[i]),v.push_back(i);}int lenv.size();char sts[v[0]];mapchar,intmp;for(int i0;ilen;i) mp[s[v[i]]];for(int i0;ilen/2;i){int lv[i],rv[len-1-i];if(s[l]!s[r])swap(s[l],s[r]);}char cs[0];int flag1;for(int i1;is.size();i){if(cs[i]) {flag0;break;}cs[i];}if(flag) {int ansv.size()-1-(mp[st]-1);printf(%d\n,ans);}else printf(-1\n);}
}
ps:其实很多时候思路无非就两种一种是模板就是前人把经验总结好你学会了他们总结的经验看到题目直接写另外一种就是你需要自己去题目中抽丝剥茧发现规律。我们对于第一种实际上都不会多想而且我们也更喜欢第一种因为我们知道它的正确性把它作为一种客观真理来用就像人有两只手我们不会一直去追问为什么人有两只手就这些都是自然而然地事情这样就减少了思考的痛苦我们只要知道即可。但是面对第二种我们对于陌生的思路就很喜欢找到一个自然而然的知识与它绑在一起仿佛这样就可以说服自己没写出这道题仅仅是因为这个知识点不知道而已。但是不是所有的题目都是水到渠成的存在对于第二种题目我们实际上很难找到那种和它完全符合的水到渠成的知识点因为模板题是有限的。所以我们永远不能用更多的学习去代替思考不是所有的题都对应一个模板。我们需要做的是抽丝剥茧一层层分析去分析题目本质去分析操作的实际意义一边分析一边去想可能的思路正着想到的思路不通倒着能不能用区间分析不通单点能不能分析明白最大值没办法入手最小值能不能写出来不断思考不断推翻不断追问很难受但是只有这样才能获得真正的令人安心的成长。题目要么就是把本质分析清楚要么就抽象出一个规律。就像b题本质就是每次选的路一定要延伸到不能延伸只有叶子节点相连才能实现规律就是叶子节点的个数除于2上取整。当然这两种方法都逃不过分析和思考尽管再难都要去进行大量的分析和思考思考是无可替代的。大量题目的练习不仅是查漏补缺去学自己不会的知识点更多的是要强迫自己不断去思考锻炼思考的能力。毫无头绪也罢痛苦难受也罢一定不要放弃思考。
这条路上你的伙伴目标可以有很多但是对手只有你自己。所以先把目光放在自己身上就像那个dfs的迷宫不断地试错总会找到正确的路而且从某种程度上来说你已经找到了不是吗。
