【连通块染色,双指针维护区间map,整除分块】CF616 CDE

迈不过友情╰ 2024-03-22 23:48 145阅读 0赞

Dashboard - Educational Codeforces Round 5 - Codeforces

C

题意:

49af3b0a152c44158d2bf750cb46f2c2.png

思路:

经典的给格子染色,直接dfs染色就行,不要用并查集,虽然也能做但是不好写

然后对于每一个*,把周围的格子的颜色扔到set里去重统计就行

Code:

  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. const int mxn=1e3+10;
  5. const int mxe=1e6+10;
  6. int N,M;
  7. int idx=0;
  8. int ans[mxn][mxn],a[mxn][mxn],mp[mxe],vis[mxn][mxn];
  9. int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
  10. string s[mxn];
  11. int F(int x,int y){
  12. return (x-1)*M+y;
  13. }
  14. bool check(int x,int y){
  15. return x>=1&&x<=N&&y>=1&&y<=M;
  16. }
  17. void dfs(int x,int y,int c){
  18. for(int i=0;i<4;i++){
  19. int vx=x+dx[i];
  20. int vy=y+dy[i];
  21. if(check(vx,vy)&&s[vx][vy]=='.'&&!a[vx][vy]){
  22. a[vx][vy]=c;
  23. mp[c]++;
  24. dfs(vx,vy,c);
  25. }
  26. }
  27. }
  28. void solve(){
  29. cin>>N>>M;
  30. for(int i=1;i<=N;i++){
  31. cin>>s[i];
  32. s[i]=" "+s[i];
  33. }
  34. for(int i=1;i<=N;i++){
  35. for(int j=1;j<=M;j++){
  36. if(s[i][j]=='.'&&!a[i][j]){
  37. a[i][j]=++idx;
  38. mp[idx]++;
  39. dfs(i,j,idx);
  40. }
  41. }
  42. }
  43. for(int i=1;i<=N;i++){
  44. for(int j=1;j<=M;j++){
  45. if(s[i][j]=='*'){
  46. set<int> S;
  47. for(int k=0;k<4;k++){
  48. int vx=i+dx[k];
  49. int vy=j+dy[k];
  50. if(check(vx,vy)&&s[vx][vy]=='.'){
  51. S.insert(a[vx][vy]);
  52. }
  53. }
  54. int res=0;
  55. for(auto u:S){
  56. res+=mp[u];
  57. }
  58. ans[i][j]=res;
  59. }
  60. }
  61. }
  62. for(int i=1;i<=N;i++){
  63. for(int j=1;j<=M;j++){
  64. if(s[i][j]=='.') cout<<".";
  65. else cout<<(ans[i][j]+1)%10;
  66. }
  67. cout<<'\n';
  68. }
  69. }
  70. signed main(){
  71. ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  72. int __=1;//cin>>__;
  73. while(__--)solve();return 0;
  74. }

D

题意:

c6a7ad52a20240849ef1ce3df1ff37af.png

思路:

很经典的双指针动态维护区间map,用set维护这个元素是否存在以及不同的种类个数,map维护每个元素的出现次数

Code:

  1. #include <bits/stdc++.h>
  2. //#define int long long
  3. using namespace std;
  4. const int mxn=5e5+10;
  5. const int mxe=1e6+10;
  6. int N,K;
  7. int a[mxn],mp[mxe];
  8. void solve(){
  9. cin>>N>>K;
  10. for(int i=1;i<=N;i++) cin>>a[i];
  11. int r=1;
  12. set<int> S;
  13. int ans=0,ansl=1,ansr=1;
  14. for(int l=1;l<=N;l++){
  15. while(r<=N){
  16. mp[a[r]]++;
  17. S.insert(a[r]);
  18. if(S.size()>K){
  19. mp[a[r]]--;
  20. if(!mp[a[r]]) S.erase(a[r]);
  21. break;
  22. }
  23. r++;
  24. }
  25. if(ans<r-1-l+1){
  26. ans=r-1-l+1;
  27. ansl=l;
  28. ansr=r-1;
  29. }
  30. mp[a[l]]--;
  31. if(!mp[a[l]]) S.erase(a[l]);
  32. }
  33. cout<<ansl<<" "<<ansr<<'\n';
  34. }
  35. signed main(){
  36. ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  37. int __=1;//cin>>__;
  38. while(__--)solve();return 0;
  39. }

E

题意:

459868bdecf94204bf260ab1eae83749.png

思路:

整除分块板子

不懂的可以看这个:整除分块 - 知乎

Code:

  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. const int mxn=5e5+10;
  5. const int mxe=1e6+10;
  6. const int mod=1e9+7;
  7. int N,M;
  8. int ksm(int a,int b,int mod){
  9. int res=1ll;
  10. while(b){
  11. if(b&1) res=(res*a)%mod;
  12. a=(a*a)%mod;
  13. b>>=1;
  14. }
  15. return res;
  16. }
  17. void solve(){
  18. cin>>M>>N;
  19. int r=1;
  20. int ans=(N%mod)*(M%mod)%mod;
  21. int inv2=ksm(2,mod-2,mod);
  22. for(int l=1;l<=min(N,M);l=r+1){
  23. r=min(M/(M/l),N);
  24. ans=(ans-(M/l)%mod*((l+r)%mod)%mod*((r-l+1)%mod)%mod*inv2%mod)%mod;
  25. }
  26. cout<<(ans+mod)%mod<<'\n';
  27. }
  28. signed main(){
  29. ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  30. int __=1;//cin>>__;
  31. while(__--)solve();return 0;
  32. }

发表评论

表情:
评论列表 (有 0 条评论,145人围观)

还没有评论,来说两句吧...

相关阅读

    相关 分块——cf1207F

    这么傻逼的题当时想了那么久 用a数组维护原序列,b\[i\]\[j\]表示 pos%i=j 的 a\[pos\]之和 对于每个修改1 x y,先直接修改a\[x\],然后枚

    相关 格子染色(区间合并)

    在二维平面上有一个无限的网格图形,初始状态下,所有的格子都是空白的。 现在有n个操作,每个操作是选择一行或一列,并在这行或这列上选择两个端点网格,把以这两个网格为端点的区间内