组合字符串
思路：
对于字符串a,从左往右,输出字典序比$b[0]$要小的字符,遇到$\geq b[0]$的字符退出.
AC Code:
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llinf=0x3f3f3f3f3f3f3f3f;
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};
void solve()
{
string a,b;
cin>>a>>b;
cout<<a[0];
for(int i=1;i<a.size();i++)
{
if((a[i]-'a')<(b[0]-'a'))cout<<a[i];
else break;
}
cout<<b[0];
cout<<endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("test.in","r",stdin);
solve();
return 0;
}
消灭老鼠
思路:
暴力/枚举.
由于只有1000个点,每个点都会和$(x_0,y_0)$,构成一条直线,而这条直线上的所有点,满足$k$相同.
因此只需要枚举直线斜率$k$就行了,但是斜率,不容易计算,但是直线上的所有点都会被一次消灭.
因此可以枚举点,对于所有满足$ (x_{0} - x_1) * (y_0 - y_2) = (x_0 - x_2) * (y_0 - y_1) $的两个点
必定在一条直线上,因此对于同一条直线上的所有点,只需要计算一次,如果说后面的点和前面的点满足这个式子就不计算.
AC Code：
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llinf=0x3f3f3f3f3f3f3f3f;
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};
int n,b,c;
struct node{
int x,y;
};
void solve()
{
cin>>n>>b>>c;
vector<node>a(n+1);
for(int i=1;i<=n;i++)
{
int x,y;
cin>>x>>y;
a[i]={x,y};
}
int ans=0;
for(int i=1;i<=n;i++)
{
bool ok=true;
for(int j=1;j<i;j++)
{
int res1=b-a[i].x,res2=c-a[i].y;
int res3=b-a[j].x,res4=c-a[j].y;
if(res1*res4==res2*res3)//如果前面计算过这种情况
{
ok=false;
break;
}
}
if(ok)ans++;
}
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;
}
树的DFS
思路：
树的遍历/思维
- 每次遍历子树的时候,把点抽出来排序一遍,在遍历.每次给当前的点记录一个访问的时间戳.
- 对于任意询问,实际上是在求一个相对值.输出映射后的值即可.
AC Code：
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llinf=0x3f3f3f3f3f3f3f3f;
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};
int e[N],ne[N],h[N],idx;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int n,m;
int mp[N];
int id[N];
int Size[N];//记录每个节点子树的大小
char In[1 << 20], *ss = In, *tt = In;
#define getchar() (ss == tt && (tt = (ss = In) + fread(In, 1, 1 << 20, stdin), tt == ss) ? EOF : *ss++)
int read (char ch = 0) {
register ll x = 0, f = 1;
while (ch < '0' || ch > '9') f = ch == '-' ? -1 : 1, ch = getchar();
while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
return x * f;
}
inline void write(ll x) {
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10ll);
putchar(x%10+48);
}
char getch (char ch = 0) {
while (ch < 'A' || (ch > 'Z' && ch < 'a') || ch > 'z') ch = getchar();
return ch;
}
inline void putch(string s)
{
for(int i=0; s[i]!='\0'; i++) putchar(s[i]);
}
int dfs(int u,int fa,int num)
{
mp[num]=u;
id[u]=num;
priority_queue<int,vector<int>,greater<int>>q;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j!=fa)q.push(j);//
}
int res=num;
while(!q.empty())
{
auto t=q.top();q.pop();
num=dfs(t,u,num+1);
}
Size[u]=num-res+1;
return num;
}
void solve()
{
n=read(),m=read();
memset(h,-1,sizeof h);
for(int i=2;i<=n;i++)
{
int fa;fa=read();
add(i,fa),add(fa,i);
}
dfs(1,-1,1);
/* for(int i=1;i<=n;i++)cout<<mp[i]<<' ';
cout<<endl;*/
/* for(int i=1;i<=n;i++)cout<<Size[i]<<' ';
cout<<endl;*/
for(int i=1;i<=m;i++)
{
int u,k;
u=read(),k=read();
if(Size[u]<k)puts("-1");
else
{
write(mp[id[u]+k-1]);
puts(" ");
}
}
return ;
}
int main()
{
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// freopen("test.in","r",stdin);
solve();
return 0;
}
