题目
A.递增三元组
题意: 给定三个数组，求有多少个三元组，满足Ai < Bj < Ck.
思路: 枚举中间那个数组，二分找即可。
(做过一次还是做错，太逆天了，每次都下意识枚举第一个数组，但是显然不满足单调性.)
时间复杂度: O(nlogn)
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
using namespace std;
#define mem(a,x) memset(a,x,sizeof(a))
#define fir(i,a,b) for(int i=a;i<=b;++i)
typedef long long ll;
typedef pair<int,int> PII;
int n,m,k,T;
vector<int> a,b,c;
ll ans = 0;
void solve()
{
cin>>n;
a = vector<int>(n); b = vector<int>(n); c = vector<int>(n);
for(int i=0;i<n;++i) cin>>a[i];
for(int i=0;i<n;++i) cin>>b[i];
for(int i=0;i<n;++i) cin>>c[i];
sort(a.begin(),a.end()); sort(b.begin(),b.end()); sort(c.begin(),c.end());
for(int i=0;i<n;++i)
{
int idx1 = upper_bound(b.begin(),b.end(),a[i])-b.begin();
if(idx1==n) continue;
int idx2 = upper_bound(c.begin(),c.end(),b[idx1]) - c.begin();
if(idx2==n) continue;
ans += 1ll*(n-idx1)*(n-idx2);
}
cout<<ans;
}
signed main(void)
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
solve();
return 0;
}
B.螺旋折线
题意: 给定一个螺旋折线，找到(x,y)是沿线走的哪个点。
思路: 终于自己独立做出来了，看来以前比现在还菜。这个是纯纯找规律，发现如果(i,i)对应的值是4ii.(我还拿错位相减推的，但是结合四个象限和平方就能观察出来)。|x|和|y|的最大值对应的那个数说明在(i,i)那一块，要么是x == i, x == -i,y == i,y == -i.分类讨论一下就好。
时间复杂度: O(1)
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
using namespace std;
#define mem(a,x) memset(a,x,sizeof(a))
#define fir(i,a,b) for(int i=a;i<=b;++i)
typedef long long ll;
typedef pair<int,int> PII;
int n,m,k,T;
ll x,y;
ll ans = 0;
void solve()
{
cin>>x>>y;
if(x == y && x >= 0)
{
ans = 4ll*(x)*(x);
}
else
{
ll mx = max(abs(x),abs(y));
ll n = mx;
ans = 4ll*(n) * (n);
if(x == n)
{
ans += n-y;
}
else if(y==-n)
{
ans += 2*n;
ans += n-x;
}
else if(y==n)
{
ans -= n-x;
}
else if(x==-n)
{
ans -= 2*n;
ans -= n-y;
}
}
cout<<ans<<endl;
}
int main(void)
{
// T = 1;
cin>>T;
while(T--)
solve();
return 0;
}
C.日志统计
题意: 略。
思路: 把每个id的点赞排序，之后二分即可。也可以双指针，不过时间复杂度级别一样的，双指针写歪了还wa了两发。
时间复杂度: O(nlogn)
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#define mem(a,x) memset(a,x,sizeof(a))
#define fir(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int N = 1e5+10;
typedef long long ll;
typedef pair<int,int> PII;
int n,m,k,T;
vector<int> va[N];
void solve()
{
cin>>n>>m>>k;
for(int i=0;i<n;++i)
{
int id; int x; cin>>id>>x;
va[x].push_back(id);
}
for(int i=0;i<N;++i)
{
if(!va[i].size()) continue;
sort(va[i].begin(),va[i].end());
for(int j=0;j<va[i].size();++j)
{
int idx = lower_bound(va[i].begin(),va[i].end(),va[i][j]+m) - va[i].begin();
idx--;
int tot = idx-j+1;
if(tot >= k)
{
cout<<i<<"\n";
break;
}
}
}
}
int main(void)
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
solve();
return 0;
}
/*
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
int n,m,k,T;
vector<int> va[N];
void solve()
{
cin>>n>>m>>k;
for(int i=0;i<n;++i)
{
int id,x; cin>>id>>x;
va[x].push_back(id);
}
for(int i=0;i<N;++i)
{
if(!va[i].size()) continue;
sort(va[i].begin(),va[i].end());
int l = 0,r = 0;
while(l < va[i].size() && r < va[i].size())
{
if(va[i][r]-va[i][l]>=m)
{
l++;
}
else
{
if(r-l+1 >= k)
{
cout<<i<<"\n";
break;
}
r++;
}
}
}
}
int main(void)
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
solve();
return 0;
}
D.全球变暖
题意: 略。
思路: bfs判一下每个连通块是否满足条件。
时间复杂度: O(n)
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#define mem(a,x) memset(a,x,sizeof(a))
#define fir(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int N = 1e5+10;
typedef long long ll;
typedef pair<int,int> PII;
int n,m,k,T;
char a[1002][1002];
int vis[1002][1002];
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
int ans = 0;
void bfs(int x,int y,int id)
{
int cnt = 0;
int tot = 0;
queue<PII> q;
q.push({x,y});
vis[x][y] = id;
while(q.size())
{
PII tmp = q.front(); q.pop();
int x = tmp.first,y = tmp.second;
cnt++;
bool flag = 0;
for(int i=0;i<4;++i)
{
int tx = x + dx[i];
int ty = y + dy[i];
if(tx<1||ty<1||tx>n||ty>n) continue;
if(vis[tx][ty]) continue;
if(a[tx][ty] == '.') {flag = 1; continue;}
vis[tx][ty] = id;
q.push({tx,ty});
}
if(flag) tot++;
}
if(tot == cnt) ans++;
}
void solve()
{
cin>>n;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
cin>>a[i][j];
}
}
int id = 0;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
if(!vis[i][j] && a[i][j] == '#')
{
bfs(i,j,++id);
}
}
}
cout<<ans;
}
int main(void)
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
solve();
return 0;
}
/*
7
.......
.##....
.##....
....##.
..####.
...###.
.......
*/
E.最大乘积
题意: 给定n个数，从中选出k个，使得乘积最大。
思路: 刚开始想复杂了，分类了很多情况。但是发现并不用(看了题解以后).
贪心就行。
(一) 如果都是负数并且k是奇数，结果只能是负数了。
(二) 否则说明存在非负数，就可以逆转正负，结果至少是个0.
如果k是奇数，把最大值先乘上，之后取出最小的两个数和最大的两个数比较乘积大小，类似归并，其实是贪心的思想了。(因为负数肯定两个最小的值乘起来大，我刚开始还想着分开放)
时间复杂度: O(nlogn)
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#define mem(a,x) memset(a,x,sizeof(a))
#define fir(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int N = 1e5+10;
typedef long long ll;
typedef pair<int,int> PII;
int n,m,k,T;
const int mod = 1000000009;
ll ans = 1;
void solve()
{
cin>>n>>k;
vector<int> a(n);
int cnt = 0;
for(int i=0;i<n;++i)
{
cin>>a[i];
if(a[i] < 0) cnt++;
}
sort(a.begin(),a.end());
if(cnt == n) //全是负数
{
if(k & 1)
{
for(int i=a.size()-1;i>=0;--i)
{
ans = ans * a[i] % mod;
}
}
else
{
for(int i=0;i<k;++i)
{
ans = ans * a[i] % mod;
}
}
if(ans < 0) ans = -((-ans)%mod);
cout<<ans; return ;
}
int l = 0,r = n-1;
if(k & 1)
{
ans = ans * a[r--];
k--;
}
while(k)
{
ll t1 = a[l] * a[l+1];
ll t2 = a[r] * a[r-1];
if(t1 > t2)
{
ans = t1 % mod * ans % mod;
l += 2;
}
else
{
ans = t2 % mod * ans % mod;
r -= 2;
}
k -= 2;
}
cout<<ans;
}
int main(void)
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
solve();
return 0;
}
/*
5 3
-100000
-10000
2
100000
10000
*/
