#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
string a;
//getline首先是cin，其次是字符串
while(getline(cin,a)){
string str;
for(auto c:a){
if(isalpha(c)) {
str += c;
}
}
stable_sort(str.begin(),str.end(),[](char a,char b){
return tolower(a)<tolower(b);
});
for(int i = 0,j = 0;i<a.size();i++){
if(isalpha(a[i])) cout<<str[j++];
else cout<<a[i];
}
cout<<endl;
}
return 0;
}
活动打卡代码
AcWing 3451. 字符串排序II
最小的k个数
思路
堆维护
代码
class Solution {
public:
vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
int n = input.size();
priority_queue<int,vector<int>,greater<int>> heap;
for(int i = 0;i<n;i++)
{
heap.push(input[i]);
}
vector<int> res;
for(int i = 0;i<k;i++)
{
res.push_back(heap.top());
heap.pop();
}
return res;
}
};
活动打卡代码
AcWing 4957. 飞机降落
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 13;
struct Node{
int begin,end,timer;
} node[N];
int t;
int n;
bool st[N];
//每一个飞机都要有一个最晚的出发时间
bool dfs(int u,int last){
//可以找到n个飞机
if(u==n) return true;
for(int i=0;i<n;i++)
{
int t = node[i].begin,d = node[i].end,l = node[i].timer;
if(!st[i] && t+d>=last){
st[i] = true;
if(dfs(u+1,max(last,t)+l)) return true;
st[i] = false;
}
}
return false;
}
int main()
{
cin>>t;
while(t--)
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>node[i].begin>>node[i].end>>node[i].timer;
}
//多个测试数据，记得要清空st，因为只会重复运行main，但是st需要手动
memset(st,0,sizeof st);
if(dfs(0,0)) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
活动打卡代码
AcWing 3480. 棋盘游戏
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 6;
int w[N][N];
int dist[N][N][5];//因为这里已经mod4
bool st[N][N][5];
struct Node{
int a;
int b;
int f;
};
int x1,y1,x2,y2;
int spfa()
{
queue<Node> q;
q.push({x1,y1,1});
memset(dist,0x3f,sizeof dist);
dist[x1][y1][1]=0;
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
while(!q.empty())
{
auto t = q.front();
q.pop();
st[t.a][t.b][t.f] = false;
for(int i=0;i<4;i++)
{
int x = t.a+dx[i],y = t.b+dy[i];
if(x<0 || x>=6 || y<0 || y>=6) continue;
int cost = t.f *w[x][y];
int s = cost%4+1;
if(dist[x][y][s] > dist[t.a][t.b][t.f]+cost){
dist[x][y][s] = dist[t.a][t.b][t.f]+cost;
if(!st[x][y][s]){
q.push({x,y,s});
st[x][y][s];
}
}
}
}
int res = 1e9;
for(int i=0;i<5;i++)
{
res = min(res,dist[x2][y2][i]);
}
return res;
}
int main()
{
for(int i=0;i<6;i++)
{
for(int j = 0;j<6;j++)
{
cin>>w[i][j];
}
}
//用一下spfa，他全都可以用，dijkstra只能用于正
cin>>x1>>y1>>x2>>y2;
cout<<spfa()<<endl;
return 0;
}
活动打卡代码
AcWing 3512. 最短距离总和
#include<iostream>
using namespace std;
const int N = 510;
int d[N][N];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j =1;j<=n;j++)
{
cin>>d[i][j];
}
}
//算法
int res = 0;
for(int k = n;k>1;k--)//当拿走最后一个点的时候，这个图中就没有元素了
{
for(int i=1;i<=n;i++)
{
for(int j = i+1;j<=n;j++)
{
if(d[i][j]>d[i][k]+d[k][j]){
d[j][i] = d[i][j] = d[i][k]+d[k][j];
}
if(i>=k &&j>=k) res+= d[i][j]*2;
}
}
}
cout<<res<<endl;
return 0;
}
亲戚
思路
牛马题，简单并查集应用，
cin和cout会超时
代码
#include<iostream>
using namespace std;
const int N =20010;
int n,m,q;
int p[N];
int find(int a){
if(p[a]!=a) p[a] = find(p[a]);
return p[a];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) p[i] = i;
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
p[find(a)] = find(b);
}
cin>>q;
while(q--)
{
int a,b;
scanf("%d%d",&a,&b);
if(find(a)== find(b)) printf("Yes\n");
else printf("No\n");
}
return 0;
}
分组统计
思路
一周了，重新写这个代码一遍过。
基本就是用数组进行存储，map进行统计。
之后对于数组进行去重，方便后续输出
然后遍历hash，找到每一组下的统计情况，然后进行输出就可以
代码
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cstring>
using namespace std;
int t;
const int N = 110;
int n;
int a[N];
int cnt[1010];
int main()
{
cin>>t;
while(t--){
cin>>n;
vector<int> v;
for(int i=0;i<n;i++){
cin>>a[i];
v.push_back(a[i]);
}
map<int,vector<int>> hash;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
hash[x].push_back(a[i]);
}
//处理后续的操作,erase是vector中的函数
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
int timer = 1;
for(auto x:hash){
memset(cnt,0,sizeof cnt);
for(auto y:x.second) cnt[y]++;
cout<<timer<<"={";
for(int i = 0;i<v.size();i++)
{
if(i!=v.size()-1) cout<<v[i]<<"="<<cnt[v[i]]<<",";
else cout<<v[i]<<"="<<cnt[v[i]];
}
cout<<"}"<<endl;
timer++;
}
}
}
高精度除法
思路
模拟实际的除法，就行
注意从高位开始的时候，后面要反转一下，除掉前导0
代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//把r作为引用是因为c++不能同时回传两个以上的参数
vector<int> div(vector<int> &A,int b,int &r){
vector<int> C;
for(int i = A.size()-1;i>=0;i--)
{
r = r*10+A[i];
C.push_back(r/b);
r = r%b;
}
//这里一趟除完了，前导0在数组的前面
reverse(C.begin(),C.end());
while(C.size()>1 && C.back()==0) C.pop_back();
return C;
}
int main()
{
string a;
int b;
cin>>a>>b;
vector<int> A;
for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
int r = 0;
auto C = div(A,b,r);
for(int i = C.size()-1;i>=0;i--) cout<<C[i];
cout<<endl;
cout<<r<<endl;
return 0;
}
活动打卡代码
AcWing 794. 高精度除法
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//把r作为引用是因为c++不能同时回传两个以上的参数
vector<int> div(vector<int> &A,int b,int &r){
vector<int> C;
for(int i = A.size()-1;i>=0;i--)
{
r = r*10+A[i];
C.push_back(r/b);
r = r%b;
}
//这里一趟除完了，前导0在数组的前面
reverse(C.begin(),C.end());
while(C.size()>1 && C.back()==0) C.pop_back();
return C;
}
int main()
{
string a;
int b;
cin>>a>>b;
vector<int> A;
for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
int r = 0;
auto C = div(A,b,r);
for(int i = C.size()-1;i>=0;i--) cout<<C[i];
cout<<endl;
cout<<r<<endl;
return 0;
}
活动打卡代码
AcWing 793. 高精度乘法
#include<iostream>
#include<vector>
using namespace std;
vector<int> mul(vector<int> &A,int b){
vector<int> C;
int t = 0;
for(int i=0;i<A.size();i++)
{
t = A[i]*b+t;
C.push_back(t%10);
t = t/10;
}
if(t) C.push_back(t);
//back取得最后一个元素，但是还在c中，pop_back是直接弹出最后一个元素
while(C.size()>1 && C.back()==0) C.pop_back();
return C;
}
int main()
{
string a;
int b;
cin>>a>>b;
vector<int> A;
for(int i = a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
auto C = mul(A,b);
for(int i =C.size()-1;i>=0;i--) cout<<C[i];
cout<<endl;
return 0;
}
