$$中北折磨王$$
思路：
这题过的挺慢的。主要是一开始没看懂样例。
后来看过的人挺多。有模拟了下样例。猜测应该是gcd。
交了gcd过了。
暴力的话 应该就是 不断迭代。当大的数是小的数的倍数的时候 输出较小的哪一个。
Code:
/*
当你觉得自己不行的时候 你就走到斑马线上 这样你就会成为一个行人
没关系 大不了我们大器晚成而已
Noe
*/
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef pair<int,int>PII;
typedef unsigned long long ull;
typedef long long LL;
const int M=2010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e5+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
void solve()
{
int a,b;
cin>>a>>b;
cout<<gcd(a,b)<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
solve();
return 0;
}
$$找最短$$
传送门
思路：
据说kmp是正解。。。
我的思路是:
- 直接考虑枚举每种$substring$ 然后检查下能不能拼回来就可以了
- 这里 因为$substring$是不断增长的所以
- 时间复杂度是$n*(1/n+2/n…+n)$括号里应该是一个级数会收敛于$logn$
- 因此时间复杂度实际是 $O(n*logn)$的 所以是能过的
Code:
/*
当你觉得自己不行的时候 你就走到斑马线上 这样你就会成为一个行人
没关系 大不了我们大器晚成而已
Noe
*/
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef pair<int,int>PII;
typedef unsigned long long ull;
typedef long long LL;
const int M=2010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=3e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
const int P=13331;
int n;
char s[N];
ull h[N],p[N];
ull get(int l,int r)
{
return h[r]-h[l-1]*p[r-l+1];
}
bool check(ull cur,int len)
{
for(int i=1;i<=n;i+=len)//从头开始判断
{//ed-i+1=len ed=len+i-1
int ed=len+i-1;
if(ed<=n)//如果没有超出
{
if(get(i,ed)==cur)continue;//如果匹配的上继续
else return false;
}else //超出了
{
if(get(i,n)==get(1,n-i+1))continue;
else return false;
}
}
return true;
}
void solve()
{
cin>>n;
cin>>s+1;
p[0]=1;
for(int i=1;i<=n;i++)//
{
h[i]=h[i-1]*P+s[i];
p[i]=p[i-1]*P;
}//字符串哈希
int ans=0;
// check(get(1,3),3);
for(int i=1;i<=n;i++)//遍历每种长度的substring
{
if(check(get(1,i),i))//由于是从前往后因此一但有满足答案的条件就是最小值
{
ans=i;
break;
}
}
cout<<ans<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("test.in","r",stdin);
solve();
return 0;
}
$我要进ACM$
传送门
这题签到题就不说了。
$$暖男zsz$$
主要知识点 破环成链 贪心 思维
思路：
比赛的时候。。一开始直接想暴力搞 但是发现取法会有后效性 应该得找最优解
错了8次以后 发现 如果从0开始枚举的话就不会有后效性了 因为这样不会有 两个人有公用的筷子
如果没有0 此时直接 $ans=\lfloor \frac{x}{2} \rfloor$
Code:
/*
当你觉得自己不行的时候 你就走到斑马线上 这样你就会成为一个行人
没关系 大不了我们大器晚成而已
Noe
*/
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef pair<int,int>PII;
typedef unsigned long long ull;
typedef long long LL;
const int M=2010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
char s[N];
void solve()
{
int n;cin>>n;
cin>>s+1;
for(int i=n+1;i<=2*n;i++)s[i]=s[i-n];
/* for(int i=1;i<=2*n;i++)cout<<s[i];
cout<<endl;*/
int pos=-1;
for(int i=1;i<=n;i++)
if(s[i]=='0')
{
pos=i;
break;
}
if(pos==-1)cout<<n/2<<endl;
else
{
int ans=0;
//x-pos+1=n;
for(int i=pos;i<=pos+n-1;i++)
if(s[i]=='1'&&s[i-1]=='1')
{
s[i]='0';
ans++;
}
cout<<ans<<endl;
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
solve();
return 0;
}
$$别走泥坑$$
传送门
思路：
首先是经典的bfs求最短路
- 由于坐标可能是负数因此需要添加偏移量 因此x和y的范围就变成了$0到1000$
- 好像可以优化一下 就是找到答案之后break下 不知道不优化会不会超时
Code
/*
当你觉得自己不行的时候 你就走到斑马线上 这样你就会成为一个行人
没关系 大不了我们大器晚成而已
Noe
*/
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef pair<int,int>PII;
typedef unsigned long long ull;
typedef long long LL;
const int M=2010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e5+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int g[2010][2010];
bool vis[2010][2010];
int dist[2010][2010];
PII ed;
int n;
void bfs()
{
queue<PII>q;
q.push({500,500});//起点入队
vis[500][500]=true;//标记
while(!q.empty())
{
int x=q.front().first;
int y=q.front().second;
q.pop();//出队
bool flag=false;
for(int i=0;i<4;i++)
{
int nx=dx[i]+x;
int ny=dy[i]+y;
if(nx>=0&&nx<=1000&&ny>=0&&ny<=1000&&!vis[nx][ny]&&g[nx][ny]!=-1)//该点能走的话
{
dist[nx][ny]=dist[x][y]+1;//距离迭代
q.push({nx,ny});//入队
vis[nx][ny]=true;//标记下
if(nx==ed.first&&ny==ed.second)
{
flag=true;//找到了
break;
}
}
}
if(flag)break;
}
}
void solve()
{
cin>>ed.first>>ed.second>>n;
ed.first+=500;
ed.second+=500;
for(int i=1;i<=n;i++)//读入坑
{
int x,y;
cin>>x>>y;
x+=500;
y+=500;//设置偏移量
g[x][y]=-1; //
}
bfs();//bfs
cout<<dist[ed.first][ed.second]<<endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
solve();
return 0;
}
$$翻译官$$
思路：
- stl的小技巧吧用tolower就行了 用cout的同学注意char不然输出的是数字
Code:
/*
当你觉得自己不行的时候 你就走到斑马线上 这样你就会成为一个行人
没关系 大不了我们大器晚成而已
Noe
*/
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef pair<int,int>PII;
typedef unsigned long long ull;
typedef long long LL;
const int M=2010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e5+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve()
{
int n;cin>>n;
string s;cin>>s;
for(auto c:s)cout<<char(tolower(c));
cout<<endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("test.in","r",stdin);
solve();
return 0;
}
