Auto

3827

Auto
3天前
#include <iostream>
#include <vector>

using namespace std;

typedef long long LL;

/*

n = p1 ^ k1 + p2 ^ k2 + ... pm ^ km

2^9 * 3^1
512*3
1536

*/

int main()
{
LL n;
cin >> n;
vector<pair<LL,int>>vec;
for(LL i = 2;i * i <= n;i ++){
if(n % i == 0){
int cnt = 0;
while(n && n % i == 0){
n = n / i;
cnt ++;
}
vec.push_back({i,cnt});
}
}

if(n != 1){

vec.push_back({n,1});
}
LL ans = 1;
for(auto &x : vec){
if(x.second % 2 == 0) continue;
ans = ans * x.first;
}
cout << ans << endl;

return 0;
}


Auto
3天前
#include <iostream>
using namespace std;

int main()
{
int n;
cin >> n;
int cnt = 0;
for(int i = 1;i < n;i ++){
if(i * i % n < (n + 1) / 2){
cnt ++;
}
}

cout << cnt << endl;

return 0;
}


Auto
3天前
#include <iostream>
using namespace std;

int main()
{
int cnt = 0;
for(int i = 0;i < 5;i ++)
{
int x;
cin >> x;
int a = x % 10;
x = x / 10;
int b = x % 10;
x = x / 10;
int c = x % 10;
int d = x / 10;

if(d == b && a - c == 1) cnt ++;
}

cout << cnt << endl;

return 0;
}


Auto
19天前
class Solution {
public:
int maxIceCream(vector<int>& costs, int coins) {
sort(costs.begin(),costs.end());
int cnt = 0;
for(auto &x : costs){
if(coins >= x){
cnt ++;
coins -= x;
}else{
break;
}
}
return cnt;
}
};


Auto
19天前
class Solution {
public:
bool checkIfPangram(string sentence) {
set<int>st;
for(auto &x : sentence){
st.insert(x);
}
return st.size() == 26;
}
};


Auto
20天前
#include <bits/stdc++.h>
using namespace std;

int main()
{
long long t;
cin >> t;
t = t / 1000;
t = t % (24 * 60 * 60);
int h,m,s;
h = t / 3600;
t = t % 3600;
m = t / 60;
t = t % 60;
s = t;
printf("%02d:%02d:%02d\n",h,m,s);

return 0;
}


Auto
20天前
class Solution {
public:
int longestBeautifulSubstring(string word) {
int ans = 0;
int cnt = 0;
map<char,int>mp;
mp['a'] = 1;
mp['e'] = 2;
mp['i'] = 3;
mp['o'] = 4;
mp['u'] = 5;
mp['z'] = 100;
for(int i = 0;i < word.size();i ++){
if(word[i] != 'a'){
cnt ++;
}else{
break;
}
}
word += 'z';

for(int i = cnt;i < word.size() - 1;i ++){
char a = word[i + 1];
char b = word[i];
int c = mp[a] - mp[b];
if(cnt == 0 && b != 'a') continue;
if(c == 0 || c == 1){
cnt ++;
}else{
if(cnt != 0)
cnt ++;
if(b == 'u'){
ans = max(ans,cnt);
}
cnt = 0;
}
// cout << cnt << endl;
}
return ans;
}

};


Auto
20天前

const int N = 1e6 + 10;
long long sum[N];
int n;
class Solution {
public:

bool check(int mid,int k)
{
for(int i = mid;i <= n;i ++){
long long a = sum[i] - sum[i - 1];

if(a * (mid) - (sum[i] - sum[i - mid]) <= k){
return true;
}
}
return false;
}

int maxFrequency(vector<int>& nums, int k) {
sort(nums.begin(),nums.end());
n = nums.size();
int l = 0,r = nums.size();
sum[0] = 0;
for(int i = 1;i <= n;i ++){
sum[i] = sum[i - 1] + nums[i - 1];
}

while(l < r){
int mid = l + r + 1 >> 1;
if(check(mid,k)){
l = mid;
}else{
r = mid - 1;
}
}
return l;
}
};


Auto
20天前
class Solution {
public:
int sumBase(int n, int k) {
int sum = 0;
while(n){
sum += n % k;
n = n / k;
}
return sum;
}
};


Auto
22天前
• L1-1
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<int>vec[N];
int k;
int ans[N];

int main()
{
cout << "To iterate is human, to recurse divine.";

return 0;
}

• L1-2

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<int>vec[N];
int k;
int ans[N];

int main()
{
cin >> n >> m >> k;
cout << n - m * k << endl;

return 0;
}

• L1-3
// 这个题有个坑点，也不算是坑点吧，题目给的是6位或者4位，我直接认为给了4位开始。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<int>vec[N];
int k;
int ans[N];

int main()
{
string str;
cin >> str;

if(str.size() == 4){
int f1 = (str[0] - '0') * 10 + str[1] - '0';
if(f1 < 22){
printf("20%02d-%c%c",f1,str[2],str[3]);
}else{
cout << 19 << f1 << '-' << str[2]  << str[3] << endl;
}
}else{
string s1;
s1 += str[0];
s1 += str[1];
s1 += str[2];
s1 += str[3];
cout << s1 << '-' << str[4] << str[5] << endl;
}

return 0;
}

• L1-4
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<int>vec[N];
int k;
int ans[N];

int main()
{
int n,m;
cin >> n >> m;
double p;
while(n --){
double x;
cin >> x;
if(x < m){
printf("On Sale! %.1lf\n",x);
}
}

return 0;
}

• L1-5
// 有个坑点就是超出了范围，题目里面明确说了，希望这个地方注意一下
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<int>vec[N];
int k;
int ans[N];

int main()
{
for(int i = 0;i < 24;i ++){
cin >> ans[i];
}
int x;
while(cin >> x && x != -1){
if(x >= 24 || x < 0) break;
if(ans[x] > 50){
printf("%d Yes\n",ans[x]);
}else{
printf("%d No\n",ans[x]);
}
}

return 0;
}

• L1-6
// 我当时没有getchar()，找了好长时间的bug
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<string>vec;
int k;
int ans[N];

int main()
{
vec.clear();
cin >> n >> k;
getchar();
for(int i = 0;i < n;i ++){
string str;

getline(cin,str);
if(str.find("easy") != -1) continue;
if(str.find("qiandao")!= -1) continue;
vec.push_back(str);
}

if(k >= vec.size()) cout << "Wo AK le" << endl;
else
cout << vec[k] << endl;

return 0;
}

• L1-7
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<int>vec;
int k;
int ans[N];

int main()
{
int n;
cin >> n;
for(int i = 0,x;i < n;i ++){
cin >> x;
vec.push_back(x);
}

sort(vec.begin(),vec.end());

int f1 = vec[0],f2 = vec[vec.size() - 1];
int cnt = 0;
for(auto &x : vec){
if(x == f1){
cnt ++;
}
}
cout << f1 << ' ' << cnt << endl;
cnt = 0;
for(auto &x : vec){
if(x == f2){
cnt ++;
}
}

cout << f2 << ' ' << cnt << endl;

return 0;
}


• L1-8
// 这个直接模拟就好了，有个点就是 >= 10，我当时写成了 > 10，差一分满分，不过立刻找出来了这个错误
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<int>vec;
int k;
int ans[N];

int main()
{
int a,b,c;
cin >> a >> b >> c;

vec.push_back(a);
vec.push_back(b);
int f1 = 0,f2 = 1;
while(vec.size() < c + 100){
int f3 = vec[f1] * vec[f2];
//  cout << f3<< endl;

if(f3 >= 10){
vec.push_back(f3 / 10);
vec.push_back(f3 % 10);
}
else{
vec.push_back(f3);
}
f1 ++;
f2 ++;
}

for(int i = 0;i < c;i ++){
if(i == c - 1){
cout << vec[i];
}else{
cout << vec[i] << ' ';
}
}

return 0;
}

• L2-1
// 我个人觉得题意有点问题，也可能是我的阅读理解不太好，就是如果栈满了话，并且此时操作的那个序列已经到头了，这视为一种无用的操作，而不是把栈顶元素放入到答案中
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m,k;
vector<pair<string,int>>vec;

int main()
{
cin >> n >> m >> k;
string str;
vec.push_back({"",0});
for(int i = 0;i < n;i ++){
cin >> str;
vec.push_back({str,0});
}

string ans;
int op;
stack<char>stk;
while(cin >> op && op != -1){

int id1 = vec[op].second;
if(id1 >= m) continue;
if(stk.size() == 0 && op == 0) continue;
if(op != 0 && stk.size() >= k){
ans += stk.top();
stk.pop();
}

if(op == 0){

ans += stk.top();
stk.pop();
}else{

int id = vec[op].second;
if(id >= m) continue;
stk.push(vec[op].first[id]);
vec[op].second ++;
}

}
cout << ans << endl;

return 0;
}
/*
3 4 100
GPLT
PATA
OMSA
3 2 3 0 1 2 0 2 2 0 -1

*/

• L2-2
// 那个字典序最小的串，有点难到我了，于是就先放了一下，先做L2-3，然后L2-310分钟左右写完了，就发现这俩好像一模两样，把所有的答案记录下来，然后按照L2-3的那个排序排个序就好了
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<int>vec[N];
int din[N];

int dist[N];
int pre[N];
int ans = 0;
vector<int>v;

void dfs(int p)
{
for(auto &x : vec[p]){
if(dist[x] <= dist[p] + 1){
dist[x] = dist[p] + 1;
pre[x] = p;
}

if(dist[x] > dist[ans]){
ans = x;
}
else if(dist[x] == dist[ans]){
if(x < ans){
ans = x;
}
}
dfs(x);
}
}

vector<int> ans1;

void dfs1(int p)
{
ans1.push_back(p);
if(pre[p] == -1) return;
dfs1(pre[p]);
}

int main()
{
memset(pre,-1,sizeof(pre));

cin >> n;
for(int i = 0;i < n;i ++){
int k;
cin >> k;
while(k --){
int x;
cin >> x;
vec[i].push_back(x);
din[x] ++;
}
}
int root;
for(int i = 0;i < n;i ++){
if(din[i] == 0){
root = i;
break;
}
}

ans = root;
dist[root] = 1;

dfs(root);
vector<vector<int>>v1;
for(int i = 0;i < n;i ++){
if(dist[i] == dist[ans]){
v.push_back(i);
dfs1(i);
reverse(ans1.begin(),ans1.end());
v1.push_back(ans1);
ans1.clear();
}
}

cout << dist[ans] << endl;

sort(v1.begin(),v1.end(),[](vector<int>p1,vector<int>p2){
int n1 = p1.size();
int n2 = p2.size();
for(int i = 0;i < n1 && i < n2;i ++){
if(p1[i] == p2[i]) continue;
return p1[i] < p2[i];
}

return n1 < n2;

});

for(int i = 0;i < v1[0].size();i ++){
if(i == v1[0].size() - 1){
cout << v1[0][i];
}else{
cout << v1[0][i] << ' ';
}
}

return 0;
}

• L2-3
// 我同学第一维有用string的，我认为这是一个好的选择
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<int>vec[N];

map<vector<int>,int>mp;

vector<pair<vector<int>,int>>v;

int main()
{
cin >> n >> m;
for(int i = 0;i < n;i ++){
for(int j = 0;j < m;j ++){
int x;
cin >> x;
vec[i].push_back(x);
}
mp[vec[i]] ++;
}

for(auto &x : mp){
v.push_back({x.first,x.second});
}

sort(v.begin(),v.end(),[](pair<vector<int>,int> p1,pair<vector<int>,int> p2){

if(p1.second == p2.second){
for(int i = 0;i < p1.first.size();i ++){
if(p1.first[i] == p2.first[i]) continue;
return p1.first[i] < p2.first[i];
}
}
return p1.second > p2.second;
});
cout << v.size() << endl;

for(auto &x : v){
cout << x.second;

for(auto &y : x.first){
cout << ' ' << y;
}
cout << endl;
}

return 0;
}


• L2-4
// 最开始做的这个题，我当时以为我是第一个A掉的，原来是我想多了。
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<int>vec[N];
int k;
int ans[N];

int main()
{
cin >> n >> m;

for(int i = 1;i <= n;i ++){
vec[i].push_back(0);
}

for(int i = 1;i <= n;i ++){
cin >> k;
for(int j = 0,x;j < k;j ++){
cin >> x;
vec[i].push_back(x);
}
}
int s = 1,cnt = 1;
for(int i = 1;i <= m;i ++){
int op,w;
cin >> op >> w;
if(op == 0){
s = vec[s][w];
}else if(op == 1){
ans[w] = s;
cout << s << endl;
s = ans[w];

}else if(op == 2){
s = ans[w];
}
}
cout << s << endl;

return 0;
}

• L3-1
• 这个题好像是卡掉spfa，我超时了一个点，，用了对优化的dijkstra，就不超时了，
• 还有一个点错的可能是n等于1的情况
• 思路:计算1各个点的最短路，这个是记录花费现金到每个地方的最小花费
• 再计算n到各个点的最短路，这个记录的是n号点用旅游金到每个点的最少花费
• 路是单向的，不要弄错了。
• 然后通过优先队列来找到目标答案
• 注意一下我这里虽然写的spfa，但是实际用的对优化的dijkstra
• 注意这个题如果不能到达的话，不能加入到答案的优先队列中
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,m,q;
const LL N = 1e6 + 10;
vector<pair<LL,pair<LL,LL>>>vec[N];
LL w[N];
const LL INF = 1e18;
bool st[N];
LL dist1[N];
LL dist2[N];

LL cost[N];

void spfa(LL *dist,LL op,LL s)
{
memset(st,0,sizeof st);
dist[s] = 0;

priority_queue<pair<LL,LL>,vector<pair<LL,LL>>,greater<pair<LL,LL>>>heap;
heap.push({0,s});

while(heap.size())
{
auto tt = heap.top();
LL t = tt.second;
heap.pop();
if(st[t]) continue;
st[t] = false;
for(auto &x : vec[t]){
LL f1 = x.first;
LL f2;
if(op == 1){
f2 = x.second.first;
}
else{
f2 = x.second.second;
}
if(dist[f1] > dist[t] + f2){
dist[f1] = dist[t] + f2;
heap.push({dist[f1],f1});
}
}
}
}

int main()
{
cin >> n >> m >> q;

for(LL i = 0;i < m;i ++){
LL a,b,c,d;
cin >> a >> b >> c >> d;
if(a == b) continue;
vec[a].push_back({b,{c,INF}});
vec[b].push_back({a,{INF,d}});
}

for(LL i = 1;i <= n;i ++){
cin >> w[i];
dist1[i] = INF;
dist2[i] = INF;
}

spfa(dist1,1,1);
spfa(dist2,2,n);

LL sum = INF;
LL s;

priority_queue<pair<LL,LL>,vector<pair<LL,LL>>,greater<pair<LL,LL>>>heap;

for(LL i = 1;i <= n;i ++){
if(dist1[i] == INF || dist2[i] == INF) continue;
cost[i] = dist1[i] + (dist2[i] + w[i] - 1) / w[i];
heap.push({cost[i],i});
}
sum = heap.top().first;
while(q --)
{
LL a,b;
cin >> a >> b;
w[a] = b;
if(dist1[a] == INF || dist2[a] == INF){
cout << sum << endl;
continue;
}
cost[a] = dist1[a] + (dist2[a] + w[a] - 1) / w[a];
heap.push({cost[a],a});

while(heap.size())
{
auto t = heap.top();
LL f1 = t.first,f2 = t.second;
if(f1 < cost[f2]){
heap.pop();
}
else{
sum = f1;
break;
}
}

cout << sum << endl;
}

return 0;
}

• L3-2
// 官方题解好像是KMP，但是我建了一个图，然后爆搜了一下，就过了
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int n;
int a[N];
int k;
vector<int>vec[N];

int g[110][110];
vector<int>ans;

bool st[N];

bool dfs(int p,int s)
{

int l1 = vec[p].size();
//  cout << p << ' ' << l1 << endl;

for(int i = 0;i < l1;i ++){
int i1 = s + i,i2 = i;
//  cout << a[i1] << ' ' << vec[p][i2] << endl;
if(a[i1] != vec[p][i2]){
return false;
}
}

if(s + l1 - 1 == n) {
return true;
}

for(int i = 1;i <= k;i ++){
if(st[i]) continue;
if(g[p][i]){
st[i] = true;
ans.push_back(i);
if(dfs(i,s + l1 - 1)){
return true;
}
ans.pop_back();

st[i] = false;
}
}
return false;
}

int main()
{

cin >> n;
for(int i = 1;i <= n;i ++)
cin >> a[i];

cin >> k;
for(int i = 1;i <= k;i ++){
int m;
cin >> m;
while(m --){
int x;
cin >> x;
vec[i].push_back(x);
}
}

unordered_set<int>stt;

for(int i = 1;i <= k;i ++){
int ed = vec[i][vec[i].size() - 1];
for(int j = 1;j <= k;j ++){
int f1 = vec[j][0];
if(ed == f1){
g[i][j] = 1;
}
if(f1 == a[1]){
stt.insert(j);
}
}
}

for(auto &x : stt){
ans.push_back(x);
st[x] = true;
if(dfs(x,1)){
break;
}
st[x] = false;
ans.clear();
}

for(int i = 0;i < ans.size();i ++){
if(i == ans.size() - 1){
cout << ans[i];
}else{
cout << ans[i] << ' ';
}
}

return 0;
}