P1142 轰炸 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
似乎数据有点小，三重循环都能过，也可以整个map然后二次循环枚举最后遍历一次也可以，特别注意的是最开始我枚举的斜率，实际上在题目要求之下需要的是三点共线，只是斜率相等并不能满足题意。
#include<bits/stdc++.h>
using namespace std;
int n,x[710],y[710];
void solve()
{
int ans,maxx=0;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
for(int i=1;i<n;i++)
{
for(int j=i+1;j<=n;j++)//分别枚举两个不同的点
{
ans=2;
for(int k=1;k<=n;k++)//找所有的点
{
if(k==i || k==j) continue;
if((x[k]-x[i])*(y[k]-y[j])==(y[k]-y[i])*(x[k]-x[j])) ans++;
}
maxx=max(maxx,ans);
}
}
printf("%d\n",maxx);
}
int main()
{
solve();
return 0;
}
这个题简单动态规划就能过了
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n=nums.size();
int dp[n];
dp[0]=nums[0];
int maxx=dp[0];
if(n==1)return nums[0];
else
{
for(int i=1;i<n;i++)
{
dp[i]=max(dp[i-1]+nums[i],nums[i]);
maxx=max(maxx,dp[i]);
}
return maxx;
}
}
};
Tasks - AtCoder Beginner Contest 332
A - Online Shopping
签到题。比cf简单些。
#include<bits/stdc++.h>
using namespace std;
long long main()
{
long long n,s,k;
cin>>n>>s>>k;
long long sum=0;
while(n--)
{
long long p,q;
cin>>p>>q;
sum+=p*q;
}
if(sum<s)sum+=k;
cout<<sum;
return 0;
}
B - Glass and Mug
我服了，思路都是一样的，但是问题就是在赋值的时候，出现了顺序问题，我先把#式进行了赋值导致*式赋值错误。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int k,g,m;//g为玻璃杯m为杯子
cin>>k>>g>>m;
int g_now=0,m_now=0;
while(k--)
{
if(g_now==g)g_now=0;
else if(m_now==0)m_now=m;
else
{
if(m_now>g-g_now)
{
m_now=m_now-g+g_now;***
g_now=g;###
}
else
{
g_now+=m_now;
m_now=0;
}
}
}
cout<<g_now<<" "<<m_now;
return 0;
}
C - T-shirts
我直接贪心做出来了，题解给的方法和我最开始做法差不多，但是vp的时候一直过不了，所以我就贪心了，贪心比较简单只要低于要求就+完事，因为是一步步来判断所以只用加1。
题解的方法就相当于在0出现之前的区间进行+。
#include<bits/stdc++.h>
using namespace std;
int n,m;
string s;
int num1,num2,now;
int main(){
cin>>n>>m>>s;
for(int i=0;i<n;i++)
{
if(s[i]=='0')
num2=0,num1=0;
else if(s[i]=='1')
{
if(num2<m)num2++;
else if(num1<now)num1++;
else now++,num1++;
}
else
{
if(num1<now)num1++;
else now++,num1++;
}
}
cout<<now;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main(void){
int n,m;
int ans=0;
int x=0,y=0;
string s;
cin>>n>>m;
cin>>s;
s+="0";
for(int i=0;i<=n;i++){
if(s[i]=='0'){
ans=max(ans,max(x+y-m,y));
x=0,y=0;
}
if(s[i]=='1')x++;
if(s[i]=='2')y++;
}
cout<<ans<<endl;
return 0;
}
532. 数组中的 k-diff 数对 - 力扣（LeetCode）
这难度也能算中等？（doge，因为有好些简单题我都想老久了）
菜鸡做法：
class Solution {
public:
int findPairs(vector<int>& nums, int k) {
int cnt=0;
if(k==0)
{
unordered_map<int,int>mp;
for(int p:nums)
{
mp[p]++;
if(mp[p]>=2)
{
cnt++;
mp[p]=-10481285;
}
}
}
else
{
sort(nums.begin(),nums.end());
nums.erase(unique(nums.begin(),nums.end()),nums.end());
int n=nums.size();
for(int i=0;i<n-1;i++)//前面的指针
{
int j=i+1;//后面的指针，注意后面的要大
while(nums[j]-nums[i]<k&&j<n)
{
j++;
}
if(nums[j]-nums[i]==k)cnt++;
}
}
return cnt;
}
};
答案1：
略胜我一成。。。。我到底在写什么啊啊啊啊啊，不过答案确实牛，拿了一个res来储存实在想不到。
class Solution {
public:
int findPairs(vector<int>& nums, int k) {
unordered_set<int> visited;
unordered_set<int> res;
for (int num : nums) {
if (visited.count(num - k)) {
res.emplace(num - k);
}
if (visited.count(num + k)) {
res.emplace(num);
}
visited.emplace(num);
}
return res.size();
}
};
答案2：
原来只需要一个哈希表或者一个双指针就能ac，我居然没想到（其实是我这样写了但没de出来，太懒了。。。没有认真想）
class Solution {
public:
int findPairs(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int n = nums.size(), y = 0, res = 0;
for (int x = 0; x < n; x++) {
if (x == 0 || nums[x] != nums[x - 1]) {
while (y < n && (nums[y] < nums[x] + k || y <= x)) {
y++;
}
if (y < n && nums[y] == nums[x] + k) {
res++;
}
}
}
return res;
}
};
来个trie树：这个算法最妙的还得是这个idx的运用和p=trie[p] [u]使其指向下一个节点
实现还是比较正常的，就是N开小了。。。
#include<bits/stdc++.h>
using namespace std;
int n;
const int N=100010;
int trie[N][26],cnt[N],idx;
char r[2];
string s;
void insert(string s)
{
int p=0;
for(int i = 0; i <s.size();i++)
{
int u=s[i]-'a';
if(!trie[p][u])trie[p][u]=++idx;
p=trie[p][u];
}
cnt[p]++;
}
int query(string s)
{
int p=0;
for(int i=0;i<s.size();i++)
{
int u=s[i]-'a';
if(!trie[p][u])return 0;
p=trie[p][u];
}
return cnt[p];
}
int main()
{
cin>>n;
while(n--)
{
cin>>r>>s;
if(r[0]=='I')insert(s);
else cout<<query(s)<<"\n";
}
return 0;
}
stl实现这个算法就更加方便了，但是需要注意字典万一会查询某一子序列出现的cnt还是trie比较好吧：
#include<bits/stdc++.h>
using namespace std;
unordered_map<string,int>mp;
int n;
char op[2];
string s;
void insert(string s)
{
mp[s]++;
}
int query(string s)
{
if(mp.find(s)!=mp.end())return mp[s];
else return 0;
}
int main()
{
cin>>n;
while(n--)
{
cin>>op>>s;
if(op[0]=='I')insert(s);
else cout<<query(s)<<"\n";
}
return 0;
}
P1706 全排列问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
利用dfs进行全排列，看了下题解发现有个佬直接递归调用main函数。。。
#include<bits/stdc++.h>
using namespace std;
int n;
const int N=10;
int a[N];
bool st[N];
void dfs(int x)
{
if(x>n)
{
for(int i=1;i<=n;i++)
{
printf("%5d",a[i]);
}
cout<<"\n";
return ;
}
for(int i=1;i<=n;i++)
{
if(!st[i])
{
a[x]=i;
st[i]=true;
dfs(x+1);
st[i]=false;
}
}
return ;
}
int main()
{
cin>>n;
dfs(1);
return 0;
}
还有个利用next_permutation做的感觉比dfs好！时间也差不了太多吧
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a[n+1];
for(int i=1;i<=n;i++)a[i]=i;
do{
for(int i=1;i<=n;i++)printf("%5d",a[i]);
cout<<endl;
}while(next_permutation(a+1,a+n+1));
return 0;
}
[P1036 NOIP2002 普及组] 选数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
一道dfs的题，说实话这两天学这个dfs只能说会用其实实际上这个代码原理并不太懂，递归回溯确实晦涩难懂
#include<bits/stdc++.h>
using namespace std;
const int N=20;
int arr[N];
int n,k;
int brr[N];
bool st[N];
int cnt;
int judge(int p)
{
for(int i=2;i<p;i++)
{
if(p%i==0)return 0;
}
return 1;
}
void dfs(int x,int start)
{
if(x>k)
{
int sum=0;
for(int i=1;i<=k;i++)
{
// cout<<brr[i]<<' ';
sum+=brr[i];
}
// cout<<endl;
cnt+=judge(sum);
return ;
}
for(int i=start;i<=n;i++)
{
if(!st[i])
{
st[i]=true;
brr[x]=arr[i];
dfs(x+1,i+1);
st[i]=false;
}
}
return ;
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>arr[i];
}
dfs(1,1);
cout<<cnt;
return 0;
}
P2089 烤鸡 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这道题和前面就不太一样了，枚举的是1 2 3递归，但是这里在复制一维数组到二维数组使用了循环，后面写了个用vector来直接复制的没想到只快了1ms。csdn了下pushback单次操作时间复杂度大约o1（maybe>)，所以以后这种情况直接遍历就好。
#include<bits/stdc++.h>
using namespace std;
int n;
const int N=11;
int a[N];
int out[60000][N];
int res;
void dfs(int x,int sum)
{
if(sum>n)return ;
if(x==N)
{
if(sum==n)
{
res++;
for(int i=1;i<=10;i++)
{
out[res][i]=a[i];
}
}
return ;
}
for(int i=1;i<=3;i++)
{
a[x]=i;
dfs(x+1,sum+i);
}
return ;
}
int main()
{
cin>>n;
if(n<10||n>30)
{
cout<<0;
return 0;
}
else dfs(1,0);
cout<<res<<"\n";
for(int i=1;i<=res;i++)
{
for(int j=1;j<N;j++)
{
printf("%d ",out[i][j]);
}
cout<<"\n";
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n;
const int N=11;
vector<int>a(11);
vector<vector<int>>out;
int res;
void dfs(int x,int sum)
{
if(sum>n)return ;
if(x==N)
{
if(sum==n)
{
res++;
out.push_back(a);
}
return ;
}
for(int i=1;i<=3;i++)
{
a[x]=i;
dfs(x+1,sum+i);
}
return ;
}
int main()
{
cin>>n;
if(n<10||n>30)
{
cout<<0;
return 0;
}
else dfs(1,0);
cout<<res<<"\n";
for(int i=0;i<res;i++)
{
for(int j=1;j<=10;j++)
{
printf("%d ",out[i][j]);
}
cout<<"\n";
}
return 0;
}
似乎做过这个贪心，排序枚举合并区间就能出
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
pair<int,int>a[N];
int n;
int cnt;
int main()
{
cin>>n;
for(int i=0;i<n;i++)cin>>a[i].first>>a[i].second;
sort(a,a+n);
for(int i=1;i<n;i++)
{
if(a[i-1].second>=a[i].first)
{
a[i].second=min(a[i-1].second,a[i].second);
}
else cnt++;
// cout<<a[i].first<<' '<<a[i].second<<endl;
}
cout<<cnt+1<<"\n";
return 0;
}
和上题一样，只是题目表达意思不一样，代码都一样
第一次用栈，开一个栈每次判断是否大于栈顶，大于栈顶就出栈，小于就说明放了一个比最开始小的数入栈，这样后面入栈判断就行
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> ans(n);
stack<int> s;
for (int i = 0; i < n; i++) {
while (!s.empty() && temperatures[i] > temperatures[s.top()]) {
ans[s.top()] = i - s.top();
s.pop();
}
s.push(i);
}
return ans;
}
};
接雨水我好像做过当时好像是用的双指针，这下用单调栈做做，和上题差不多的入栈出栈，然后需要在出栈后计算雨水总和l就是左边的横坐标，r就是当前（右边的坐标）然后宽度就能得出，再找高度就行h=min(右墙高度, 左墙高度)-低处高度
class Solution {
public:
int trap(vector<int>& height) {
int ans = 0;
stack<int> st;
for (int i = 0; i < height.size(); i++)
{
while (!st.empty() && height[st.top()] < height[i])
{
int cur = st.top();
st.pop();
if (st.empty()) break;
int l = st.top();
int r = i;
int h = min(height[r], height[l]) - height[cur];
ans += (r - l - 1) * h;
}
st.push(i);
}
return ans;
}
};
[P1596 USACO10OCT] Lake Counting S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<iostream>
using namespace std;
const int N=110;
int n,m;
char g[N][N];
bool st[N][N];//true已淹没，false未淹没
int res;
int dx[]={1,1,1,0,0,-1,-1,-1};
int dy[]={-1,0,1,1,-1,1,0,-1};
void dfs(int x,int y)
{
for(int i=0;i<8;i++)
{
int a=x+dx[i],b=y+dy[i];
//1.越界
if(a<0||b<0||a==n||b==m) continue;
//2.已淹没
if(st[a][b]) continue;
//3.非平地
if(g[a][b]!='W') continue;
st[a][b]=true;
dfs(a,b);
}
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
{
scanf("%s",g[i]);
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(g[i][j]=='W'&&!st[i][j])
{
st[ai[j]=true;
dfs(i,j);
res++;
}
}
}
cout<<res<<endl;
return 0;
}
B3625 迷宫寻路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include <iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=110;
int n,m;
char g[N][N];
int dist[N][N];
typedef pair<int,int> PII;
queue<PII>q;
int dx[]={1,0,-1,0};
int dy[]={0,-1,0,1};
int bfs(int x,int y)
{
q.push({x,y});
while(q.size())
{
auto t=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int a=t.first+dx[i],b=t.second+dy[i];
if(a>n||b>m||a<1||b<1)continue;
if(dist[a][b])continue;
if(g[a][b]=='#')continue;
dist[a][b]=dist[t.first][t.second]+1;
q.push({a,b});
if(a==n&&b==m)return 1;
}
}
return 0;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%c",&g[i][j]);
}
}
if(bfs(1,1))cout<<"Yes";
else cout<<"No";
return 0;
}
P1443 马的遍历 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include <iostream>
#include <queue>
using namespace std;
const int N=410;
int g[N][N];
bool st[N][N];
typedef pair<int,int> PII;
queue<PII>q;
int n,m,x,y;
int dx[]={1,1,2,2,-1,-1,-2,-2};
int dy[]={2,-2,1,-1,2,-2,1,-1};
void bfs(int x,int y)
{
g[x][y]=0;
st[x][y]=true;
q.push({x,y});
while(q.size())
{
auto t=q.front();
q.pop();
for(int i=0;i<8;i++)
{
int a=t.first+dx[i],b=t.second+dy[i];
if(a<1||b<1||a>n||b>m)continue;
if(st[a][b])continue;
q.push({a,b});
g[a][b]=g[t.first][t.second]+1;
st[a][b]=true;
}
}
}
int main()
{
cin>>n>>m>>x>>y;
bfs(x,y);
for(int i=1;i<=n;i++)
{
for (int j = 1; j <= m; j++)
{
if(st[i][j])printf("%-5d", g[i][j]);
else printf("%-5d",-1);
}
printf("\n");
}
return 0;
}
P2404 自然数的拆分问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<cstdio>
#include<iostream>
#include<cstdlib>
using namespace std;
int a[10001]={1},n;
int search(int,int);
int print(int);
int main()
{
cin>>n;
search(n,1);//将要拆分的数n传递给s
return 0;
}
int search(int s,int t)
{
int i;
for(i=a[t-1];i<=s;i++)
if(i<n)//当前数i要大于等于前一位数，且不超过n
{
a[t]=i;//保存当前拆分的数i
s-=i;//s减去数i，s的值将继续拆分
if(s==0)print(t);//当s=0时，拆分结束输出结果
else search(s,t+1);//当s>0时，继续递归
s+=i;//回溯：加上拆分的数，以便产生所有可能的拆分
}
}
int print(int t)
{
for(int i=1;i<=t-1;i++)//输出一种拆分方案
cout<<a[i]<<"+";
cout<<a[t]<<endl;
}
Dashboard - Codeforces Round 916 (Div. 3) - Codeforces
A. Problemsolving Log
cf题意真难懂啊，这题就看字母出现次数一次统计就行，等于就cnt++就行
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
string s;
cin>>s;
int cnt=0;
unordered_map<char,int>mp;
for(int i=0;i<n;i++)
{
mp[s[i]]++;
if(mp[s[i]]==s[i]-'A'+1)cnt++;
}
cout<<cnt<<endl;
}
return 0;
}
B. Preparing for the Contest
其实就只需要构造升序为特定长度的数组即可，来个排序一步到位
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
int a[n];
for(int i=0;i<n;i++)
{
a[i]=n-i;
}
sort(a,a+k+1);
for(int i=0;i<n;i++)
{
cout<<a[i]<<' ';
}
cout<<"\n";
}
return 0;
}
C. Quests
预处理a前缀和，b前缀最大值，每次选最大的就行
#include <iostream>
#include <vector>
using namespace std;
int main() {
int t;
cin>>t;
while(t--)
{
int n, k;
cin >> n >> k;
vector<int> a(n + 1);
vector<int> b(n + 1);
vector<int> max_b(n+1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
cin >> b[i];
max_b[i]=max(b[i],max_b[i-1]);
}
int presum[n+1];
presum[1]=a[1];
int out=0;
for(int i=2;i<=n;i++)presum[i]=presum[i-1]+a[i];
for(int i=1;i<=n;i++)
{
if(k>=i)out=max(presum[i]+(k-i)*max_b[i],out);//这里打比赛时写撇了，补题发现把i<=k作为for的条件是最好
}
cout<<out<<endl;
}
return 0;
}
D. Three Activities
用pair存储a[i],b[i],c[i]及其编号i，sort一下然后暴力更新max_sum，我的问题主要在最后三重循环那里，一直没想到3——3——3必能出答案
#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
vector<int> a(n), b(n), c(n);
vector<pair<int, int>> pa(n), pb(n), pc(n);
for(int i = 0; i < n; ++i) {
cin >> a[i];
pa[i] = { a[i], i };
}
for(int i = 0; i < n; ++i) {
cin >> b[i];
pb[i] = { b[i], i };
}
for(int i = 0; i < n; ++i) {
cin >> c[i];
pc[i] = { c[i], i };
}
sort(pa.begin(), pa.end(), greater<>());
sort(pb.begin(), pb.end(), greater<>());
sort(pc.begin(), pc.end(), greater<>());
int j = 0, k = 0, l = 0;
long long maxsum = 0;
for(j = 0; j < 3; j++)
{
for(k = 0; k < 3; k++)
{
for(l = 0; l < 3; l++)
{
if(pa[j].second != pb[k].second &&pa[j].second != pc[l].second &&pb[k].second != pc[l].second)
{
maxsum = max(maxsum, (long long)(pa[j].first +pb[k].first+pc[l].first));
}
}
}
}
cout << maxsum << '\n';
}
}
E1. Game with Marbles (Easy Version)
补这个题时发现数据很小，然后dfs跑一遍应该可以
E2. Game with Marbles (Hard Version)
E1,E2都是下面这个代码，推一下就行
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
struct node {
int x, y;
int sum;
};
node a[N];
bool cmp(node m, node n) {
return m.sum > n.sum;
}
int main() {
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i].x;
for (int i = 1; i <= n; i++) cin >> a[i].y, a[i].sum = a[i].x + a[i].y;
sort(a + 1, a + 1 + n, cmp);
long long sum = 0;
for (int i = 1; i <= n; i++)
{
if (i % 2 == 1) sum += a[i].x - 1;
else sum -= a[i].y - 1;
}
cout << sum << endl;
}
return 0;
}
Dashboard - Codeforces Round 805 (Div. 3) - Codeforces
别问为什么突然805了，问就是跳了）
A. Round Down the Price
签到题找规律就行
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t ;
cin>>t;
while(t--)
{
int n;
cin>>n;
int cnt=0;
while(pow(10,cnt)<=n)cnt++;
cout<<n-(int)pow(10,cnt-1)<<endl;
}
return 0;
}
B. Polycarp Writes a String from Memory
果断模拟
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
string s;
cin>>s;
unordered_map<char,int>mp;
int flag=0,cnt=0;
for(int i=0;i<s.size();i++)
{
mp[s[i]]++;
if(mp.size()==4)mp.erase(mp.begin(),mp.end()) , mp[s[i]]++,cnt++;
}
if(mp.size()!=0)cnt++;
cout<<cnt<<endl;
}
return 0;
}
C. Train and Queries
思路简单，找到first station和last station比较就行，不过这题怎么这么恶心最开始用unordered_map直接tle了n发，问了下wrzgg换map直接就过了？？？？？！！！！！！！！我已经觉得unordered_map是史了
#include<bits/stdc++.h>
using namespace std ;
int main()
{
int t;
cin >> t ;
while(t--)
{
int n,k;
cin>>n>>k;
map<int,int>num,f,l;
for(int i=0;i<n;i++)
{
scanf("%d",&num[i]);
if(f.find(num[i])==f.end())f[num[i]]=i,l[num[i]]=i;
else
{
l[num[i]]=i;
}
}
int p,q;
while(k--)
{
scanf("%d%d",&p,&q);
if(f.find(p)==f.end()||f.find(q)==f.end())cout<<"NO\n";
else
{
if(f[p]<l[q])cout<<"YES\n";
else cout<<"NO\n";
}
}
}
return 0;
}
D. Not a Cheap String
直接模拟就能过
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
string s;
cin>>s;
int k;
cin>>k;
int sum=0;
int n=s.size();
map<char,int>mp;
for(int i=0;i<n;i++)
{
mp[s[i]]++;
sum+=s[i]-'a'+1;
}
for(char ch='z' ;ch>='a'&&sum>k;ch--)
{
while(mp[ch]>0&&sum>k)
{
sum-=ch-'a'+1;
mp[ch]--;
}
}
string out="";
for(char ch:s)
{
if(mp[ch]>0)
{
out+=ch;
mp[ch]--;
}
}
cout<<out<<endl;
}
return 0;
}