网站开发人员岗位职责,江都建设局网站李局,手机 pc网站模板,锦州网站做优化就写了两个题#xff0c;以为要掉分#xff0c;结果早上起来发现还上分了#xff08;说明wtcl
A - Rainbow Dash, Fluttershy and Chess Coloring
无论边长是奇数还是偶数#xff0c;考虑每次操作最外层的一圈#xff0c;一个人操作一圈的一般#xff0c;然后另一个人就…就写了两个题以为要掉分结果早上起来发现还上分了说明wtcl
A - Rainbow Dash, Fluttershy and Chess Coloring
无论边长是奇数还是偶数考虑每次操作最外层的一圈一个人操作一圈的一般然后另一个人就能够把这一圈涂满而且还能继续操作最外圈。每次2人操作后问题变成边长-2的情况。稍微思考一下就可。
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#includeiostream
#includealgorithm
using namespace std;
int n;
int main()
{IO;int T;cinT;while(T--){cinn;if(n1)cout(n-3)/22endl;elsecout(n-2)/22endl;}return 0;
}B - Applejack and Storages
统计4的倍数和2的倍数。其中既是4的倍速也是2的倍数只看做4的倍数。
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#includeiostream
#includealgorithm
using namespace std;
const int N100010;
int mp[N];
int n,q;
int main()
{IO;cinn;int x0,y0;for(int i1;in;i){int a;cina;mp[a];if(mp[a]%20) y;//加完后是2的倍数if(mp[a]%40) x,y-2; //加完后是4的倍数要把二的倍数减去}cinq;while(q--){char op;int a;cinopa;if(op){mp[a];if(mp[a]%20) y;if(mp[a]%40) x,y-2;}else{if(mp[a]%20) y--;//减之前是2的倍数 2的倍数减小一个if(mp[a]%40) x--,y2;//减之前是4的倍数 4的倍数减小一个2的倍数最终应该增加一个由于上面减了一个要加二个这点wa了2发mp[a]--;}if(x1y2||x2) coutYESendl;else coutNOendl;}return 0;
}C - Pinkie Pie Eats Patty-cakes
最小距离最大?二分?做题的时候我就发现二分的check函数好像不容易写。如果能够写出check函数其实好像不用二分直接答案就出来了。 果不其然群友说这就是个贪心题后来想了想果然是。1111222233334445566789 比如上述序列构造方式如下 1234569 123457 123468 123 如果是11111222233334445566789 123469 12346 12357 12458 13 因此有以下贪心
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#includeiostream
#includealgorithm
#includecstring
using namespace std;
const int N100010;
int mp[N],n;
int main()
{IO;int T;cinT;while(T--){cinn;int mx0;memset(mp,0,sizeof mp);for(int i1;in;i){int a;cina;mp[a];mxmax(mx,mp[a]);}int cnt0;for(int i0;iN;i)if(mp[i]mx) cnt;coutcnt(n-cnt*mx)/(mx-1)-1endl;}return 0;
}D-Rarity and New Dress
悬线dp第一次听说一定要把这题补了 解法一二分抄代码题解 维护菱形中间点先求上下最长维护左右最长不能超过上下最长
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#define debug(x) cout#x: x
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
const int N2010;
int n,m;
ll ans;
int u[N][N],d[N][N],l[N][N],r[N][N];
int h[N][N];
char s[N][N];
int main()
{IO;cinnm;for(int i1;in;i) cins[i]1;// 预处理for(int j1;jm;j){for(int i1;in;i){if(s[i][j]s[i-1][j]) u[i][j]u[i-1][j]1;else u[i][j]1;}for(int in;i;i--){if(s[i][j]s[i1][j]) d[i][j]d[i1][j]1;else d[i][j]1;}for(int i1;in;i) h[i][j]min(d[i][j],u[i][j]);}for(int i1;in;i){for(int j1;jm;j){if(s[i][j]s[i][j-1]) l[i][j]min(l[i][j-1]1,h[i][j]);else l[i][j]1;}for(int jm;j;j--){if(s[i][j]s[i][j1]) r[i][j]min(r[i][j1]1,h[i][j]);else r[i][j]1;}}// 求答案for(int i1;in;i)for(int j1;jm;j)ansmin(l[i][j],r[i][j]);coutansendl;return 0;
}解法二 这个菱形可以看成4个等腰直角三角形维护等腰直角三角形即菱形中心点 f[i][j]表示s[i][j]为直角顶点最大等腰直角三角形。4次dp
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#define debug(x) cout#x: x
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
const int N2010;
int n,m;
ll ans;
int f1[N][N],f2[N][N],f3[N][N],f4[N][N];
char s[N][N];
int main()
{IO;cinnm;for(int i1;in;i) cins[i]1;for(int i1;in;i)for(int j1;jm;j){f1[i][j]1;if(s[i][j]s[i-1][j]s[i][j]s[i][j-1]) f1[i][j]min(f1[i-1][j],f1[i][j-1])1;}for(int i1;in;i)for(int jm;j;j--){f2[i][j]1;if(s[i][j]s[i-1][j]s[i][j]s[i][j1]) f2[i][j]min(f2[i-1][j],f2[i][j1])1;}for(int in;i;i--)for(int j1;jm;j){f3[i][j]1;if(s[i][j]s[i1][j]s[i][j]s[i][j-1]) f3[i][j]min(f3[i1][j],f3[i][j-1])1;}for(int in;i;i--)for(int jm;j;j--){f4[i][j]1;if(s[i][j]s[i1][j]s[i][j]s[i][j1]) f4[i][j]min(f4[i1][j],f4[i][j1])1;}for(int i1;in;i)for(int j1;jm;j) ansmin(min(f1[i][j],f2[i][j]),min(f3[i][j],f4[i][j]));coutansendl;return 0;
}
