1.Contest2411 – 毕老师算法 A 作业一
传送门在这里
题目总览:
A. 进制转换
#include<iostream>
using namespace std;
long Revert(long x)
{
long ans = 0;
long mutiply = 1;
while(x)
{ans += ((x%8) * mutiply);
mutiply *= 10;
x /= 8;
}
return ans;
}
int main()
{
int x, ans;
cin>>x;
ans = Revert(x);
cout<<ans<<endl;
return 0;
}B. 排列问题
// B. 排列问题
#include<bits/stdc++.h> // 奇怪之处就在于基本上所有的代码只有用了这个头文件就不再写其余头文件了。using namespace std;
vector<string> ans;
void Perm(string str, int low, int high)
{if(low == high)
{ans.push_back(str);
return;
}
for(int i=low; i<=high; ++i)
{if(i>0 && str[i]==str[i-1]) continue; // 判断反复
swap(str[i], str[low]);
Perm(str, low+1, high);
swap(str[i], str[low]);
}
}
int main()
{
string str;
cin>>str;
str.pop_back();
sort(str.begin(), str.end());
Perm(str, 0, str.size()-1);
sort(ans.begin(), ans.end());
for(const auto x:ans) cout<<x<<" ";
system("pause");
return 0;
}C. 疾速幂
#include<bits/stdc++.h>
using namespace std;
const long long mm = 100000007;
typedef long long ll;
ll mostfastPow(ll base, ll power)
{
ll result = 1;
while(power>0)
{if(power&1)
{
power = power - 1;
result = result * base % mm;
}
power >>= 1;
base = base * base % mm;
}
return result;
}
ll myPow(int x)
{
ll ans = 0;
for(int i=1; i<=x; ++i)
{ans += mostfastPow(i, i);
}
return (ans+1)%mm;
}
int main()
{
int x;
while(scanf("%d", &x))
{cout<<myPow(x)<<endl;
}
return 0;
}
// 参考文章:https://blog.csdn.net/qq_19782019/article/details/85621386?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522163080391116780261989580%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=163080391116780261989580&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-85621386.first_rank_v2_pc_rank_v29&utm_term=%E5%BF%AB%E9%80%9F%E5%B9%82&spm=1018.2226.3001.4187D. 求第 k 小
// D. 求第 k 个小的数
#include<bits/stdc++.h>
using namespace std;
int Partition(int a[], int low, int high);
template<class Type>
int RandomizedPartition(Type a[], int p, int r);
template<class Type>
void RandomizedQuickSort(Type a[], int p, int r);
template<class Type>
Type RandomizedSelect(Type a[], int p, int r, int k);
int main()
{int a[100], n;
while(~scanf("%d", &n))
{memset(a, 0, sizeof(a));
for(int i=0; i<n; i++) scanf("%d",&a[i]);
int k;
scanf("%d", &k);
cout<<RandomizedSelect(a, 0, n-1, k)<<endl;
}
system("pause");
return 0;
}
// 2.RandomizedSelect, 均匀工夫复杂度 O(n)
int Partition(int a[], int low, int high)
{int key = a[low];
while(low<high)
{while(low<high&&a[high]>key) --high;
a[low] = a[high];
while(low<high&&a[low]<=key) ++low;
a[high] = a[low];
}
a[low] = key;
return low;
}
template<class Type>
int RandomizedPartition(Type a[], int p, int r)
{int i = rand()%(r-p+1) + p;
swap(a[i], a[p]);
return Partition(a, p, r);
}
// template<class Type>
// void RandomizedQuicksort(Type a[], int p, int r) // 随机快排
// {// if(p<r)
// {// int q = RandomizedPartition(a, p, r);
// RandomizedQuicksort(a, p, q-1); // 对左半段排序
// RandomizedQuicksort(a, q+1, r); // 对右半段排序
// }
// }
template<class Type>
Type RandomizedSelect(Type a[], int p, int r, int k) // 随机划分, 抉择
{if(p == r) return a[p];
int loc = RandomizedPartition(a, p ,r);
int count = loc-p+1; //count 为 a[p:loc]中的元素个数
if(k<=count) return RandomizedSelect(a, p, loc, k);
else return RandomizedSelect(a, loc+1, r, k-count);
}E. 沙子的品质
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int a[1005],sum[1005]={0};
int f[1005][1005];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++){cin>>a[i];
}
// 初始化赋值为最大值
memset(f,inf,sizeof(f));
for(int i=1;i<=n;i++){f[i][i]=0;
sum[i]=sum[i-1]+a[i];
}
// 区间 dp，首先确定区间长度 len, 区间长度便是动静布局的阶段。for(int len=2;len<=n;len++){ // 阶段：区间长度 len
for(int L=1;L<=n-len+1;L++){ // 状态左端点 L 取值范畴
int r=L+len-1; // 区间右端点 r
for(int k=L;k<r;k++){ // 决策, 连接点 k
f[L][r]=min(f[L][k]+f[k+1][r]+sum[r]-sum[L-1],f[L][r]);
}
}
}
cout<<f[1][n]<<endl;
system("pause");
return 0;
}F. 最长公共子序列
// F. 最长公共子序列
#include<bits/stdc++.h>
using namespace std;
int longestCommonSubsequence(string a, string b)
{int M = a.size();
int N = b.size();
vector<vector<int>> dp(M+1, vector<int>(N+1, 0));
for(int i=1; i<=M; ++i)
{for(int j=1; j<=N; ++j)
{if(a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1]+1;
else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[M][N];
}
int main()
{
string a, b;
cin>>a>>b;
cout<<longestCommonSubsequence(a, b)<<endl;
system("pause");
return 0;
}G.sort
// Sort
#include<bits/stdc++.h>
using namespace std;
const int Maxn = 1000001;
int a[Maxn];
int main()
{
int n, m;
while(~scanf("%d%d", &n, &m))
{memset(a, 0, sizeof(a));
for(int i=0; i<n; ++i)
{
int t;
scanf("%d", &t);
a[500000 + t] = 1;
}
for(int i=Maxn; m>0; --i)
{if(a[i])
{if(m>1) printf("%d", i-500000);
else printf("%d\n", i-500000);
m--;
}
}
}
return 0;
}H.Joseph
// 约瑟夫环
#include<bits/stdc++.h>
using namespace std;
const int maxn = 15;
int num[maxn];
int main()
{for(int i=1; i<=14; ++i)
{
int m = i+1; // 报号数从 i + 1 开始
int sum = i*2; // 总人数 sum
int j,pre=0,cur=0; //pre 示意之前杀死的一个人,cur 示意以后杀死的人的地位
for(j = 0 ; j < i ; ++j) // 一共要杀死 i 集体
{cur = (pre+m-1)%(sum-j); //sum- j 示意残余的人数 // 牢记此表达式! cur = (pre+m-1)%(sum-j)
if(cur<i) // 杀到了坏蛋, 重置所有变量, 报号数 ++
{
j=-1; // 如果 for 循环中 j 初始为 0 的话, 此处应该 j 为 -1, 因为马上就要 ++ j 了
pre=0;
cur=0;
m++;
}
pre=cur;
}
num[i] = m; // 记录答案
}
int k;
while(scanf("%d",&k)!=EOF,k)
printf("%d\n",num[k]);
}I.Factstone Benchmark
// Factstone 等级被定义为这样的最大整数 n，使得 n！能够示意为一个计算机字中的无符号整数（比方 1960 年的 4 位计算机可示意 3！=6，而不能示意 4！=24）。// n! < pow(2, m) m 为多少位计算机, 求出最大的 n 值
// 应用对数计算 ln(n!) < mlog(2) 大大减少数值 即 ln(n)+ln(n-1)+...+ln(1) < mln(2)
#include<bits/stdc++.h>
using namespace std;
int Rating(int year)
{int m = pow(2, (year-1940)/10);
cout<<m<<endl;
double ans = 0;
int n = 1;
while(ans<m*log(2))
{ans += log(n);
cout<<"ans:"<<ans<<endl;
n++;
}
return n-2;
}
int main()
{
int year;
while(cin>>year)
{if(year==0) break;
cout<<Rating(year)<<endl;
}
cout<<log(2)<<endl;
system("pause");
return 0;
}
// 打表法
#include <stdio.h>
#include <cmath>
/*int main(){
double sum;
for (int i = 4, j = 0; j <= 20; i *= 2, j++){
int k = 1;
sum = 0;
while (sum < i){sum += log2(k);
k++;
}
printf("%d\n", k - 2);
}
}*/
int main(){
int year;
int ans[21] = { 3, 5, 8, 12, 20, 34, 57, 98, 170, 300, 536, 966, 1754,
3210, 5910, 10944, 20366, 38064, 71421, 134480, 254016 };
while (scanf("%d", &year) && year != 0){getchar();
year = (year - 1960) / 10;
printf("%d\n", ans[year]);
}
return 0;
}
J.Ants
// J.Ants
// 我傻了, 很简略的问题: 蚂蚁相遇之后往相同方向走, 其实并没有什么影响, 因为蚂蚁若是依照原方向走原本还是要走这么远, 只是换了一只蚂蚁走而已.
// 咱们不必要关怀具体的蚂蚁, 不论它相遇不相遇, 其实后果就是一样的, 咱们能够认为是放弃原样交织而过
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int num;
cin>>num;
while(num--)
{
int len,n;
int max1=0,min1=0;
cin>>len>>n;
for(int i=0;i<n;i++)
{
int pos;
cin>>pos;
max1 = max(max1, max(pos, len-pos)); // 找每只蚂蚁间隔两端的最大值 max(pos, len-pos), 在这些最大值外面找到最大的
min1 = max(min1, min(pos, len-pos)); // 找每只蚂蚁间隔两端的最小值 min(pos, len-pos), 在这些最小值外面找到最大的
}
cout<<min1<<" "<<max1<<endl;
}
system("pause");
return 0;
}K.Matches Game
// Bouton 定理: 先手可能在非均衡尼姆博弈中取胜，而后手可能在均衡的尼姆博弈中取胜。// 具体解释请拜访: [乔治的编程小屋 --- 尼姆博弈](http://www.pgcode.top/2021/09/16/%e5%b0%bc%e5%a7%86%e5%8d%9a%e5%bc%88/)
#include<iostream>
using namespace std;
int main()
{
int n, a;
while(scanf("%d", &n)!=EOF)
{
int ans = 0;
for(int i=0; i<n; ++i)
{scanf("%d", &a);
ans ^= a;
}
if(ans) printf("Yes\n");
else printf("No\n");
}
system("pause");
return 0;
}L.Sort2
// Sort2
#include<bits/stdc++.h>
using namespace std;
const int Maxn = 1000001;
int a[Maxn];
int main()
{
int n, m;
while(~scanf("%d%d", &n, &m))
{for(int i=0; i<n; ++i)
{
int t;
scanf("%d", &t);
a[500000+t]++;
}
for(int i=Maxn; m>0; --i)
{if(a[i])
{for(int j=0; j<a[i]; ++j)
{if(m>1) printf("%d", i-500000);
else printf("%d\n", i-500000);
m--;
}
}
}
}
return 0;
}2.Contest2417 – 毕老师算法 A 作业二
传送门在这里
题目总览:
A. 单词排序
// A. 单词排序
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
int n;
cin>>n;
vector<string> vec;
string str;
for(int i=0; i<n; ++i)
{
cin>>str;
vec.push_back(str);
}
sort(vec.begin(), vec.end());
for(const auto x:vec) cout<<x<<" ";
system("pause");
return 0;
}B. 求数组的最长递加子序列
// B. 求数组的最长递加子序列(留神不是不递增序列)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
// DP
int PosOfLDS(vector<int> &nums, vector<int> &memo) // 返回最长递加子序列最初一个元素的下标, 而后
{int n = nums.size();
if(n == 0) return 0;
vector<int> dp(n, 1);
// vector<int> memo(n, -1);
for(int i=0; i<n; ++i)
{for(int j=0; j<i; ++j)
{if(nums[i] < nums[j])
{dp[i] = max(dp[j]+1, dp[i]);
memo[i] = j;
}
}
}
for(const int x:dp) cout<<x<<" ";
cout<<endl;
for(const int x:memo) cout<<x<<" ";
cout<<endl;
// return *max_element(dp.begin(), dp.end()); // 记住不是 return 最初一个 dp[n-1]!!!
return max_element(dp.begin(), dp.end()) - dp.begin();}
void PrintOfLDS(vector<int> &nums, vector<int> &memo, int pos)
{if(memo[pos] == -1)
{cout<<nums[pos]<<" ";
return;
}
else
{PrintOfLDS(nums, memo, memo[pos]);
cout<<nums[pos]<<" ";
}
}
int main()
{
int n;
while(~scanf("%d", &n))
{vector<int> nums(n);
for(int i=0; i<n; ++i) scanf("%d", &nums[i]);
// cout<<LengthOfLDS(nums)<<endl;
vector<int> memo(n, -1);
int max_pos = PosOfLDS(nums, memo);
PrintOfLDS(nums, memo, max_pos);
}
system("pause");
return 0;
}
// // 办法二. 找出与降序排好的数组的最长公共子序列
// const int Size = 1010; // 尽量用全局变量
// int DP[Size][Size];
// int DIR[Size][Size];
// bool compare(int a, int b) // 降序排列
// {
// return a>b;
// }
// int LCS_length(vector<int> &a, vector<int> &b)
// {// int M = a.size();
// int N = b.size();
// for(int i=1; i<=M; i++)
// {// for(int j=1; j<=N; j++)
// {// if(a[i-1] == b[j-1])
// {// DP[i][j] = DP[i-1][j-1] + 1;
// DIR[i][j] = 1;
// }
// else if(DP[i-1][j] >= DP[i][j-1])
// {// DP[i][j] = DP[i-1][j];
// DIR[i][j] = 2;
// }
// else
// {// DP[i][j] = DP[i][j-1];
// DIR[i][j] = 3;
// }
// }
// }
// return DP[M][N];
// }
// void LCS(vector<int> &a, int i, int j)
// {// if(i==0 || j==0) return;
// if(DIR[i][j] == 1)
// {// LCS(a, i-1, j-1);
// cout<<a[i-1]; //a[i-1]==b[j-1]
// }
// else if(DIR[i][j]==2) LCS(a, i-1, j);
// else if(DIR[i][j]==3) LCS(a, i, j-1);
// }
// int main()
// {
// int n;
// while(scanf("%d", &n) && n)
// {// int a[n], b[n];
// for(int i=0; i<n; i++)
// {// scanf("%d", a+i);
// b[i] = a[i];
// }
// for(int i=0; i<n; i++) cout<<a[i];
// cout<<endl;
// for(int i=0; i<n; i++) cout<<b[i];
// cout<<endl;
// sort(a, a+n, compare);
// for(int i=0; i<n; i++) cout<<a[i];
// cout<<endl;
// vector<int> A(a, a+n), B(b, b+n);
// cout<<LCS_length(A, B)<<endl;
// LCS(A, n, n);
// cout<<endl;
// }
// system("pause");
// return 0;
// }C. 矩形滑雪场
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 100;
int r, c;
int max_len[maxn][maxn], mp[maxn][maxn];
int get_len(int i, int j) {if (max_len[i][j]) {return max_len[i][j];
}
int max_neighbor = 0;
if (i-1 >= 0 && mp[i][j] > mp[i-1][j]) {max_neighbor = max(max_neighbor, get_len(i-1, j));
}
if (i+1 < r && mp[i][j] > mp[i+1][j]) {max_neighbor = max(max_neighbor, get_len(i+1, j));
}
if (j-1 >= 0 && mp[i][j] > mp[i][j-1]) {max_neighbor = max(max_neighbor, get_len(i, j-1));
}
if (j+1 < c && mp[i][j] > mp[i][j+1]) {max_neighbor = max(max_neighbor, get_len(i, j+1));
}
max_len[i][j] = max_neighbor + 1;
return max_len[i][j];
}
int main() {// freopen("test.txt", "r", stdin);
cin >> r >> c;
int i, j;
for (i=0; i<r; ++i) {for (j=0; j<c; ++j) {cin >> mp[i][j];
}
}
int res = 0;
for (i=0; i<r; ++i) {for (j=0; j<c; ++j) {res = max(res, get_len(i, j));
}
}
cout<<res<<endl;
}D.Homework
#include<bits/stdc++.h>
using namespace std;
bool cmp(pair<double, double> a, pair<double, double> b)
{return a.second/a.first > b.second/b.first;}
int main()
{
int M, N;
while(scanf("%d%d", &M, &N) && (M && N))
{
vector<pair<double, double>> vec;
double time, value;
for(int i=0; i<M; ++i)
{scanf("%lf%lf", &time, &value);
vec.push_back(pair<double, double>(time, value));
}
sort(vec.begin(), vec.end(), cmp);
double TimeTotal = N;
double ValueTotal = 0; //double 类型, 如果写为 int 类型答案谬误
for(const auto x:vec) cout<<"("<<x.first<<","<<x.second<<")"<<endl;
for(const pair<double, double> x:vec)
{if(TimeTotal-x.first >= 0)
{
cout<<"Flag1"<<endl;
ValueTotal += x.second;
TimeTotal -= x.first;
}
else
{
ValueTotal += TimeTotal * x.second/x.first;
break;
}
}
printf("%.2lf\n", ValueTotal);
}
system("pause");
return 0;
}E. 区间蕴含问题
// E. 区间蕴含问题
// 贪婪算法 相似于流动安顿问题
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10010;
struct Node
{int left, right;}node[maxn];
bool cmp(Node a, Node b)
{return a.right < b.right;}
int main()
{
int n, m;
scanf("%d %d", &n, &m);
for(int i=0; i<n; ++i)
{scanf("%d %d", &node[i].left, &node[i].right);
// node[i].right++;
}
sort(node, node+n, cmp);
int l, r;
for(int i=0; i<m; ++i)
{scanf("%d %d", &l, &r);
int pos = l, ans = 0;
for(int j=0; j<n; ++j)
{if(node[j].left>=pos && node[j].right<=r)
{
cout<<l<<" "<<r<<endl;
cout<<j<<""<<node[j].left<<" "<<node[j].right<<endl;
ans++;
pos = node[j].right;
}
}
printf("%d\n", ans);
}
system("pause");
return 0;
}F. 最长子序列
// F. 最长子序列(最大子段和)
#include<bits/stdc++.h>
using namespace std;
// 1. 递归分治法
// f(i) = max(f(i-1)+nums[i], nums[i]) 思考 f(i-1)带来的是正能量还是负能量
// f(i) 代表以第 i 个数结尾的「间断子数组的最大和」，那么很显然咱们要求的答案就是：// max(0-i-1){f[i]}
int maxSubArray(vector<int> &nums)
{int n = nums.size();
if(n==0) return {};
if(n==1) return nums[0];
vector<int> f(n);
f[0] = nums[0];
for(int i=1; i<n; ++i)
{f[i] = max(f[i-1]+nums[i], nums[i]);
}
for(const int x:f) cout<<x<<" ";
cout<<endl;
return *max_element(f.begin(), f.end()); // 记住不是返回 f[n-1]
}
int maxSubArray2(vector<int> &nums)
{int n = nums.size();
if(n==0) return {};
int pre = 0, maxAns = nums[0];
for(const int x:nums)
{pre = max(pre+x, x); //pre 记录以后 x 后面的间断子数组的最大和, 即 f[i-1], 不断更新. 相似于滚动数组
maxAns = max(maxAns, pre);
}
return maxAns;
}
int main()
{
int n;
while(~scanf("%d", &n))
{vector<int> nums(n);
for(int i=0; i<n; ++i) scanf("%d", &nums[i]);
cout<<maxSubArray(nums)<<endl;
}
system("pause");
return 0;
}G. 元素整除问题
// G. 元素整除问题
#include<bits/stdc++.h>
using namespace std;
// O(n^2)
int main()
{int a[20];
for(int i=0; i<20; i++) scanf("%d", &a[i]);
sort(a, a+20);
for(int i=1; i<20; i++)
{for(int j=0; j<i; j++)
{if(a[i]%a[j] == 0)
{printf("%d\n", a[i]);
break;
}
}
}
system("pause");
return 0;
}H. 渊子赛马
// H. 渊子赛马
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
while(scanf("%d", &n) && n)
{int *a = new int[n], *b = new int[n];
for(int i=0; i<n; ++i) scanf("%d", &a[i]);
for(int i=0; i<n; ++i) scanf("%d", &b[i]);
sort(a, a+n);
sort(b, b+n);
int count = 0;
int pos = 0;
for(int i=0; i<n; ++i)
{for(int j=pos; j<n; ++j)
{if(a[j]>b[i]) // 找到一个最近的大于 b[i]的
{
count++;
pos = j;
cout<<"count:"<<count<<"pos:"<<pos<<"a[j]:"<<a[j]<<"b[i]:"<<b[i]<<endl;
break;
}
}
if(pos==n-1) break;
}
if(count > n/2) printf("YES\n");
else printf("NO\n");
}
system("pause");
return 0;
}I.The hardest problem ever
// I.żČöĂÜÂë
#include<bits/stdc++.h>
using namespace std;
int main()
{freopen("I_in.txt","r",stdin);
freopen("I_out2.txt","w",stdout);
// string model = "VWXYZABCDEFGHIJKLMNOPQRSTU";
string str;
while(cin>>str)
{if(str=="ENDOFINPUT") break;
if(str=="START") continue;
if(str=="END")
{printf("\n");
continue;
}
for(int i=0; i<str.length(); ++i)
{// if(isalpha(str[i])) str[i] = model[(str[i]-'A')%26];
if(isalpha(str[i])) str[i] = 'A' + (str[i]-'A'+21)%26;
}
cout<<str<<" ";
}
system("pause");
return 0;
}J.Rock-Paper-Scissors Tournament
// J.Rock-Paper-Scissors Tournament
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define mm(a) memset(a, 0, sizeof(a));
int i, j, n, k;
string s;
int t = 0;
int win[105] = {0};
int lose[105] = {0};
int main()
{// freopen("J_in.txt", "r", stdin);
// freopen("J_out.txt", "w", stdout);
while(1)
{scanf("%d%d", &n, &k);
if(n==0) break;
mm(win); mm(lose);
if(t++) printf("\n");
for(i=0; i<k*n*(n-1)/2; ++i)
{
int p1 = 0, p2 = 0;
char s1[10]={0}, s2[10]={0};
scanf("%d %s %d %s", &p1, s1, &p2, s2);
if(s1[0]==s2[0]) continue;
else if(s1[0]=='r'&&s2[0]=='s' || s1[0]=='s'&&s2[0]=='p' || s1[0]=='p'&&s2[0]=='r')
{win[p1]++, lose[p2]++;}
else
{win[p2]++, lose[p1]++;}
}
for(int i=1; i<=n; ++i)
{if(win[i]+lose[i]) printf("%d: %.3f\n", i, 1.0*win[i]/(win[i]+lose[i]));
else printf("-\n");
}
}
return 0;
}K.Balloon Robot
// K.Balloon Robot
#include<bits/stdc++.h>
using namespace std;
/*
假如初始机器人从地位 1 开始, 计算做完每道题总共有多少不开心值
将不开心值从小到大排序
而后枚举每一道题解出时，机器人就在座位旁的状况。对于第 i 道题目, 因为地位往后走, 前面的题目的工夫就会缩小 tid[i], 后面的题目的工夫就会减少 m -tid[i].
因而递推式是 sum - (p-i)*tid[i] + i*(m-tid[i])
= sum + m * (i - 1) - tid[i] * p;
*/
typedef long long ll;
const int N = 2e5+10;
ll tid[N], id[N]; //id 数组用来记录每个队伍所在的地位
int main()
{freopen("K_in.txt","r",stdin);
int t;
scanf("%d", &t); // 测试用例组数
while(t--)
{
ll n, m, p;
scanf("%lld%lld%lld", &n, &m, &p); // n 个队伍，m 个地位，一共解决了 p 个题目
for(int i=1; i<=n; ++i)
scanf("%lld",&id[i]); // n 个队伍别离在哪几个地位
ll ans=1e18, sum = 0;
for(int i=1; i<=p; i++)
{
ll a,b;
scanf("%lldlld", &a, &b);
tid[i] = (id[a]-1-b+m)%m; // 计算不开心值, 不开心值 = 地位 a - 第一个地位 -AC 的工夫
sum += tid[i];
}
sort(tid+1, tid+p+1);
for(int i=1; i<=p; ++i)
ans = min(ans, sum+m*(i-1)-tid[i]*p); //sum = sum-(p-i)*tid[i]+i*(m-tid[i]) = sum+m*(i-1)-tid[i]*p
printf("%lld\n", ans);
}
}2.Contest2420 – 毕老师算法 A 作业三
传送门在这里
题目总览:
A.Brackets Sequence
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define INF 0x3f3f3f3f
using namespace std;
int f[105][105],pos[105][105];
char s[105];
void fun(int x,int y)
{if(x>y) return;
if(x==y){if(s[x]=='('||s[x]==')') printf("()");
if(s[x]=='['||s[x]==']') printf("[]");
}
else if(x<y){if(pos[x][y]==-1){if(s[x]=='('){printf("(");
fun(x+1,y-1);
printf(")");
}
else{printf("[");
fun(x+1,y-1);
printf("]");
}
}
else{fun(x,pos[x][y]);
fun(pos[x][y]+1,y);
}
}
}
int main()
{scanf("%s",s);
memset(f,0,sizeof(f));
int len=strlen(s);
for(int i=len;i>0;i--){s[i]=s[i-1];
f[i][i]=1;
}
for(int l=1;l<=len;l++){for(int i=1;i<=len-l;i++){
int j=l+i;
f[i][j]=INF;
if((s[i]=='('&& s[j]==')')||(s[i]=='['&&s[j]==']')){if(f[i+1][j-1]<f[i][j]) f[i][j]=f[i+1][j-1];
}
pos[i][j]=-1;
for(int k=i;k<j;k++){if(f[i][k]+f[k+1][j]<f[i][j]){f[i][j]=f[i][k]+f[k+1][j];
pos[i][j]=k;
}
}
}
}
fun(1,len);
printf("\n");
return 0;
}B.Dollars
// B.Dollars
#include<bits/stdc++.h>
using namespace std;
int money[] = {1, 2, 4, 10, 20, 40, 100, 200, 400, 1000, 2000}; // 除以五,1 美元等于 100 美分
const int N = 6010;
long long f[N];
int main()
{std::ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// 打表法
f[0] = 1;
for(int i=0; i<=10; i++)
for(int j=money[i]; j<=6000; j++)
f[j] += f[j-money[i]];
double ans;
while(cin>>ans && ans!=0)
{int pos = (ans*100)/5;
printf("%6.2lf%17lld\n", ans, f[pos]);
}
return 0;
}C.Longest Match
// C.Longest Match
#include<bits/stdc++.h>
using namespace std;
vector<string> split(string str) // 将一个字符串从空格处离开, 非字符也算作空格
{
vector<string> vec;
int len = str.length();
bool flag = true; // 示意一个新单词开始与否
int start = 0; // 每个单词开始的下标
for(int i=0; i<len; ++i)
{if(flag && isalpha(str[i]))
{
flag = false;
start = i;
}
else if(!isalpha(str[i]))
{
flag = true;
vec.push_back(str.substr(start, i-start));
}
}
if(flag == false) vec.push_back(str.substr(start, len-start)); // 最初一个为字母的话
return vec;
}
int LongestMatch(vector<string> &vec1, vector<string> &vec2)
{int len1 = vec1.size(), len2 = vec2.size();
int ans = 0;
for(int i=0; i<len2; ++i)
{if(find(vec1.begin(), vec1.end(), vec2[i]) != vec1.end()) ans++;
}
return ans;
}
int main()
{
string str1, str2;
int i = 1;
while(getline(cin, str1) && getline(cin, str2))
{if(str1.empty() || str2=="")
{printf("%2d.",i++);
cout<<"Blank!"<<endl;
continue;
}
vector<string> vec1, vec2;
vec1 = split(str1);
vec2 = split(str2);
printf("%2d.",i++);
cout<<"Length of longest match:"<<LongestMatch(vec1, vec2)<<endl;
}
// getline(cin, str1);
// vector<string> vec1 = split(str1);
// for(const auto x:vec1) cout<<x<<endl;
// cout<<endl;
system("pause");
return 0;
}
D.History Granding
#include<bits/stdc++.h>
using namespace std;
int order[30];
int node[30],arry[30][30];
int main()
{
int num;
cin>>num;
int i,j,k;
for(i=0;i<num;i++)
{
cin>>k;
order[k-1]=i+1;
}
while(cin>>k)
{node[k-1]=1;
for(i=1;i<num;i++)
{
cin>>k;
node[k-1]=i+1;
}
memset(arry,0,sizeof(arry));
for(i=1;i<=num;i++)
{for(j=1;j<=num;j++)
{if(node[i-1]==order[j-1]) arry[i][j]=arry[i-1][j-1]+1;
else arry[i][j]=max(arry[i-1][j],arry[i][j-1]);
}
}
cout<<arry[num][num]<<endl;
}
return 0;
}E. 滑雪
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int n ,m;
struct node{
int x;
int y;
int data;
};
bool cmp(node a, node b){return a.data < b.data;}
bool check(int x, int y){if( x >= 1 && y >= 1 && x <= n && y <= m)
return 1;
else
return 0;
}
int main (){int high[105][105];
int maxLen[105][105];
int to[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int ans = 1;
cin >> n >> m;
int k = 0;
node s[10006];
for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){scanf("%d", &high[i][j]);
s[++k].data = high[i][j];
s[k].x = i;
s[k].y = j;
maxLen[i][j] = 1;
}
}
sort(s + 1, s + k + 1, cmp);
for(int i = 1 ; i <= k; i++){
int x1, y1;
for(int j = 0; j < 4; j++){int x = s[i].x;
int y = s[i].y;
x1 = x + to[j][0];
y1 = y + to[j][1];
if(check(x1, y1)){if(high[x][y] > high[x1][y1]){maxLen[x][y] = max(maxLen[x1][y1] + 1, maxLen[x][y]);
ans = max(ans, maxLen[x][y]);
}
}
}
}
cout << ans << endl;
return 0;
}F.Wavio Sequence
// Wavio Sequence
// 贪婪算法 + 二分查找 求最长回升子序列的长度 O(nlogn)
// 思考一个简略的贪婪，如果咱们要使回升子序列尽可能的长，则咱们须要让序列回升得尽可能慢，因而咱们心愿每次在回升子序列最初加上的那个数尽可能的小。// 保护一个一维数组 B，并且这个数组是动静扩大的，初始大小为 1,B[i]示意最长回升子序列长度是 i 的所有子串中开端最小的那个数，// 咱们顺次遍历数组 nums 中的每个元素，并更新数组 B 和 len 的值。如果 nums[j] > B[len] 则更新 len = len + 1
// 否则在 B[1...len] 中 找到 B[i-1] < nums[j] < B[i]的 pos 值, 而后更新 B[i] = nums[j]
#include<bits/stdc++.h>
using namespace std;
const int inf = 10000;
int lengthOfLIS(vector<int> &nums, int end) // 失去数组 nums[1..end]的最大回升子序列长度
{int n = nums.size();
if(n 0) return 0;
vector<int> B(n+1, 0);
B[1] = nums[0];
int len = 1; // 记录最长回升子序列的长度
for(int i=1; i<end; ++i)
{if(nums[i] > B[len]) B[++len] = nums[i];
else
{
int l = 1, r = len, pos = 0;
while(l <= r)
{int mid = (l+r) >> 1;
if(B[mid] < nums[i])
{
pos = mid;
l = mid+1;
}
else r = mid-1;
}
B[pos+1] = nums[i];
}
}
return len;
}
int Ans(vector<int> &nums)
{int n = nums.size();
vector<int> LIS_length;
vector<int> LIS_length_Reverse;
for(int i=1; i<=n; i++)
LIS_length.push_back(lengthOfLIS(nums, i)); // i 为 end, 所以 i <=n
reverse(nums.begin(), nums.end()); // 反转数组
for(int i=1; i<=n; i++)
LIS_length_Reverse.push_back(lengthOfLIS(nums, i));
for(int i=0; i<n; ++i)
{if(LIS_length[i]) LIS_length[i] = -inf;
if(LIS_length_Reverse[i]==1) LIS_length_Reverse[i] = -inf;
}
int max_ans = 1;
for(int i=0; i<n; ++i)
max_ans = max(max_ans, LIS_length[i]+LIS_length_Reverse[n-i-1]-1);
return max_ans;
}
int main()
{
int n;
while(cin>>n && n)
{vector<int> nums(n);
for(int i=0; i<n; i++) cin>>nums[i];
cout<<Ans(nums)<<endl;
}
return 0;
}G.FatMouse’s Trade
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int N,M;
struct node{
int x,y;
double s;
}a[1000];
double cmp(node aa,node bb){return aa.s>bb.s;}
int main(){
double sum,ans;
while(~scanf("%d %d",&M,&N)){if(M==-1&&N==-1) break;
for(int i=0;i<N;i++){scanf("%d %d",&a[i].x,&a[i].y);
a[i].s=(1.0*a[i].x/a[i].y);
}
sort(a,a+N,cmp);
sum=0.0,ans=0.0;
for(int i=0;i<N;i++){if(sum<=M){if(sum+a[i].y<=M){ans+=a[i].x;
sum+=a[i].y;
}
else{ans+=a[i].s*(M-sum);
sum=M;
}
}
else {break;}
}
printf("%.3lf\n",ans);
}
return 0;
}H.Schedule
// Schedule
// 贪婪算法
// 题目粗心: 有 N 个时间表，他们别离有本人的开始工夫和完结工夫，// 同时，也有很多机器，时间表上的工夫是应用机器的工夫，然而，// 一台机器不能在反复的工夫被应用，所以，要实现时间表的工作，可能须要多台机器，// 题目要求的就是符合要求的起码机器数和相应工夫之和(机器期待的工夫也算)。#include<bits/stdc++.h>
using namespace std;
struct Node
{
int T;
int flag; // 1 示意该节点是开始工夫,2 示意是完结工夫
}nodes[200000];
bool cmp(Node &a, Node &b)
{if(a.T != b.T) return a.T<b.T;
else return a.flag > b.flag;
}
int main()
{
int x;
scanf("%d", &x);
while(x--)
{
int count;
int pos = 0; // 示意节点数组的地位
int machine = 0;
int ans_mach = 0;
long long ans_sum = 0;
stack<int> endtime; // 完结时刻寄存在栈中
scanf("%d", &count);
while(!endtime.empty()) endtime.pop(); // 保障 endtime 数组清空
for(int i=0; i<count; i++)
{scanf("%d", &nodes[pos].T);
scanf("%d", &nodes[pos+1].T);
nodes[pos].flag = 1;
nodes[pos+1].flag = 2;
ans_sum = ans_sum + (nodes[pos+1].T - nodes[pos].T); // 先把所有工作工作的工夫累加
pos += 2;
}
sort(nodes, nodes+pos, cmp); // 从小到大排序
for(int i=0; i<pos; i++)
{if(nodes[i].flag == 1)
{
machine++;
if(!endtime.empty())
{int t = endtime.top();
endtime.pop();
ans_sum += (nodes[i].T - t); // 咱们并不关怀位于栈顶这个完结工夫所对应的开始工夫是哪个, 因为计算等待时间只须要直到完结工夫即可. 而且依据大小排序之后, 能够保障, 新退出的这个开始工夫肯定能够在任意一台曾经有的机器上工作!(因为目前所有的完结工夫都是小于该开始工夫的, 所以这也是一个咱们不须要关怀 (开始_完结) 对应的一个起因.)
}
}
else
{
machine--;
endtime.push(nodes[i].T);
}
ans_mach = max(ans_mach, machine); // 更新最大机器数
}
printf("%d %lld\n", ans_mach, ans_sum);
}
system("pause");
return 0;
}I.Gene Assembly
#include <bits/stdc++.h>
using namespace std;
int n;
struct p
{int start,end,pos;}s[1000];
bool cmp(p a,p b)
{return a.end<b.end;}
int main()
{while(scanf("%d",&n) && n)
{for(int i = 0; i < n; i++)
{s[i].pos = i + 1;
scanf("%d%d",&s[i].start,&s[i].end);
}
sort(s,s+n,cmp);
int t=0;
for(int i = 0; i < n; i++)
if(t<s[i].start)
{t = s[i].end;
printf("%d%c",s[i].pos,(i==n-1)?'\n':' ');
}
}
return 0;
}(～~▽~)～
除了几个题因为工夫缘故或者是太难了的起因不是本人写的, 其余的都是本人的劳动成果. 因为最近工夫缓和, 题解就不写了.
如果大家感觉本篇文章对本人有所帮忙的话, 无妨去我的集体博客 — 乔治的编程小屋逛逛吧, 置信你会发现更精彩的内容.