Sierpinski carpet
1.这道题的核心其实在于，我们要观察到点的位置是在每一个小图形的正方形内，和一个大图型的中心正方形处的，那么通过观察可以发现，如果满足在这个正方形处，那么一定(3k-1+1) <= x,y<=(2*3k-1)
2.这个k是什么意思呢？当我们n=3的时候k可以取1，2，3，也就是对应每一级的中间宫格，于是我们对每个位置（x，y）进行判断，找到会包含这个点的大小最小的k级地毯，如果处于中间宫格就输出".",否则考虑这个坐标在k-1级地毯的相对位置（x mod 3k-1,y mod3k-1）,递归判断
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
int dx[]={0,1,-1,0};
int dy[]={-1,0,0,1};
int pow3[15];
bool check(int i,int j)
{
int k=10;
while(k>=2&&pow3[k-1]>=i&&pow3[k-1]>=j) k--;//对每个坐标找到最小的宫格图
//当x，y在下面这个范围内，说明在中心宫格处，
if(i>=pow3[k-1]+1&&i<=2*pow3[k-1]&&j>=pow3[k-1]+1&&j<=2*pow3[k-1]) return 0;
if(k==1) return 1;//其实每个#对应的宫格图最小应该为1级也就是3*3型的
return check(i%pow3[k-1],j%pow3[k-1]);//一次没找到最小就继续找
}
//总体还是用递归的思想来解决这道题，不断去找这个坐标所属于的最小级的图
void solve()
{
int n;
cin>>n;
pow3[0]=1;
for(int i=1;i<=10;i++) pow3[i]=3*pow3[i-1];
for(int i=1;i<=pow3[n];i++)
{
for(int j=1;j<=pow3[n];j++)
{
if(check(i,j)) cout<<"#";
else cout<<".";
}
cout<<endl;
}
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}
Consecutive
1.题意就是简单的找有几个两个连在一起且相同的字母串而已，由于是3e5，所以n2的方法是过不去的
2.我把字符串符合条件的下标都放进数组里，然后二分查找lower_bound题目要求的l，r然后找到的两个下标相减就是答案
快狠狠的点它
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
int dx[]={0,1,-1,0};
int dy[]={-1,0,0,1};
void solve()
{
string s;
int n,q;
cin>>n>>q;
cin>>s;
vector<int>ve;
for(int i=0;i<s.size()-1;i++)
{
if(s[i]==s[i+1]) ve.push_back(i+1);
}
while(q--)
{
int l,r;
cin>>l>>r;
int ans=0;
int k1=lower_bound(all(ve),l)-ve.begin();
int k2=lower_bound(all(ve),r)-ve.begin();
ans=k2-k1;
cout<<ans<<endl;
}
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}
1.二分答案的题目，其实很好写就是check里要注意一下
2.在check里我们的思路是，把宽度用完看行数符不符合，但是要注意如果有一个特别大的值，让总和等于初始值，记得让行数变为1e9。
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
int dx[]={0,1,-1,0};
int dy[]={-1,0,0,1};
int n,m;
vector<int>ve;
bool check(int x)
{
int sum=-1,now=1;//-1是因为加第一个单词是不需要空格的
for(int i=0;i<n;i++)
{
if(ve[i]>x) now=1e10;//有一个数特别大，大于宽度了，就没办法满足直接让now=1e10
if(sum+ve[i]+1<=x) sum+=ve[i]+1;
else {
sum=ve[i];
now++;
}
}
if(now<=m) return 1;
else return 0;
}
void solve()
{
cin>>n>>m;
for(int i=0;i<n;i++){
int x;
cin>>x;
ve.push_back(x);
}
int l=0,r=1e18;
while(l<r)
{
int mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<l;
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}