class OrderedStream {
public:
map<int,string>mp;
int ptr=1;
public:
OrderedStream(int n) {
}
vector<string> insert(int idKey, string value) {
vector<string>ans;
mp.insert({idKey,value});
while(mp.find(ptr)!=mp.end())
{
ans.push_back(mp[ptr]);
ptr++;
}
return ans;
}
};
活动打卡代码
LeetCode 1656. 设计有序流
活动打卡代码
LeetCode 641. 设计循环双端队列
class MyCircularDeque {
private:
deque<int>dq;
int maxx;
public:
MyCircularDeque(int k) {
maxx=k;
}
bool insertFront(int value) {
if(dq.size()==maxx)return false;
dq.push_front(value);
return true;
}
bool insertLast(int value) {
if(dq.size()==maxx)return false;
dq.push_back(value);
return true;
}
bool deleteFront() {
if(dq.empty())return false;
dq.pop_front();
return true;
}
bool deleteLast() {
if(dq.empty())return false;
dq.pop_back();
return true;
}
int getFront() {
if(dq.empty())return -1;
return dq.front();
}
int getRear() {
if(dq.empty())return -1;
return dq.back();
}
bool isEmpty() {
if(dq.empty())return true;
return false;
}
bool isFull() {
if(dq.size()==maxx)return true;
return false;
}
};
活动打卡代码
AcWing 4405. 统计子矩阵
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
typedef long long LL;
LL s[N][N];
int n,m,k;
LL cnt;
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)//列的前缀和
for(int j=1;j<=m;j++)
{
scanf("%d",&s[i][j]);
s[i][j]+=s[i-1][j];
}
for(int i=1;i<=n;i++)//枚举上下界
for(int j=i;j<=n;j++)
{
int sum=0;
for(int l=1,r=1;r<=m;r++)
{
sum+=s[j][r]-s[i-1][r];
while(sum>k)
{
sum-=s[j][l]-s[i-1][l];
l++;
}
cnt+=r-l+1;
}
}
cout<<cnt<<endl;
return 0;
}
活动打卡代码
AcWing 4405. 统计子矩阵
普通前缀和
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
typedef long long LL;
int g[N][N];
LL s[N][N];
int n,m,k;
LL cnt;
void check(int row,int line)
{
for(int i=row;i<=n;i++)
for(int j=line;j<=m;j++)
{
int t=s[i][j]-s[i][j-line]-s[i-row][j]+s[i-row][j-line];
if(t<=k)cnt++;
}
}
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)//前缀和
for(int j=1;j<=m;j++)
{
scanf("%d",&g[i][j]);
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+g[i][j];
}
for(int i=1;i<=n;i++)//枚举矩阵
for(int j=1;j<=m;j++)
{
check(i,j);
}
cout<<cnt<<endl;
return 0;
}
前缀和+双指针
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
typedef long long LL;
LL s[N][N];
int n,m,k;
LL cnt;
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)//列的前缀和
for(int j=1;j<=m;j++)
{
scanf("%d",&s[i][j]);
s[i][j]+=s[i-1][j];
}
for(int i=1;i<=n;i++)//枚举上下界
for(int j=i;j<=n;j++)
{
int sum=0;
for(int l=1,r=1;r<=m;r++)//
{
sum+=s[j][r]-s[i-1][r];
while(sum>k)
{
sum-=s[j][l]-s[i-1][l];
l++;
}
cnt+=r-l+1;
}
}
cout<<cnt<<endl;
return 0;
}
活动打卡代码
LeetCode 768. 最多能完成排序的块 II
class Solution {
public:
int maxChunksToSorted(vector<int>& arr) {
int res=0;
int n=arr.size();
unordered_map<int,int>cnt;
vector<int>sorted=arr;
sort(sorted.begin(),sorted.end());
for(int i=0;i<n;i++)
{
int x=arr[i],y=sorted[i];
cnt[x]++;
if(cnt[x]==0)cnt.erase(x);
cnt[y]--;
if(cnt[y]==0)cnt.erase(y);
if(cnt.size()==0)res++;
}
return res;
}
};
活动打卡代码
LeetCode 1282. 用户分组
class Solution {
public:
vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
vector<vector<int>>ans;
unordered_map<int,vector<int>>g;
int n=groupSizes.size();
for(int i=0;i<n;i++)
{
g[groupSizes[i]].push_back(i);
}
for(auto& [x,t]:g)
{
int siz=t.size();
int i=0;
while(i!=siz)
{
vector<int>tmp;
for(int j=0;j<x;j++)
{
tmp.push_back(t[i++]);
}
ans.push_back(tmp);
}
}
return ans;
}
};
class Solution {
public:
vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
vector<vector<int>>ans;
map<int,vector<int>>mp;
int n=groupSizes.size();
for(int i=0;i<n;i++)
{
mp[groupSizes[i]].push_back(i);
if(mp[groupSizes[i]].size()==groupSizes[i])
{
ans.push_back(mp[groupSizes[i]]);
mp[groupSizes[i]].clear();
}
}
return ans;
}
};
活动打卡代码
AcWing 179. 八数码
#include <iostream>
#include <cstring>
#include <algorithm>
#include<unordered_map>
#include<queue>
using namespace std;
const int N=10;
int dx[]={-1,1,0,0};//上下左右
int dy[]={0,0,-1,1};
string g,seq;
char n;
string endd="12345678x";
int f(string state)
{
int dist=0;
for(int i=0;i<9;i++)
{
if(state[i]!='x')
{
int t=state[i]-'1';
dist+=abs(t/3-i/3)+abs(t%3-i%3);
}
}
return dist;
}
string bfs(string start)
{
priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>>heap;//优先队列，存到终点的距离
unordered_map<string,int>dist;//起点到此状态的距离
unordered_map<string,pair<string,char>>pre;//存储此状态的上一个状态
char op[]="udlr";
heap.push({f(start),start});
dist[start]=0;
while(heap.size())
{
auto t=heap.top();
heap.pop();
if(t.second==endd)break;
int x,y;
for(int i=0;i<9;i++)
if(t.second[i]=='x')
{
x=i/3,y=i%3;
break;
}
string state=t.second;
string source=state;
for(int i=0;i<4;i++)
{
int nx=x+dx[i],ny=y+dy[i];
if(nx<0||nx>=3||ny<0||ny>=3)continue;
swap(state[nx*3+ny],state[x*3+y]);
if(!dist.count(state)||dist[state]>dist[source]+1)
{
dist[state]=dist[source]+1;
pre[state]={source,op[i]};
heap.push({dist[state]+f(state),state});
}
swap(state[nx*3+ny],state[x*3+y]);
}
}
string res;
while(endd!=start)
{
res+=pre[endd].second;
endd=pre[endd].first;
}
reverse(res.begin(),res.end());
return res;
}
int main()
{
while(cin>>n)
{
g+=n;
if(n!='x')seq+=n;
}
int t = 0;
for (int i=0; i<8;i++ )
for (int j=i+1; j<8;j++)
if (seq[i]>seq[j])
t++ ;
if(t%2)cout<<"unsolvable"<<endl;//A*算法必须保证答案有解
else cout<<bfs(g)<<endl;
return 0;
}
活动打卡代码
工程课 Linux-7.9. homework_9
ipython3 # 打python3交互环境
res = 2**112 + 3**78
! echo $res > ans.txt # ! 表示后面的内容是shell脚本 ??
