共计 18125 个字符，预计需要花费 46 分钟才能阅读完成。
1.Contest2425 – 毕老师算法试验一
传送门在这里
题目总览:
A. 排列问题
// 排列问题
// 输出一个可能含有反复字符的字符串，打印出该字符串中所有字符的全排列。#include<bits/stdc++.h>
using namespace std;
bool IsSwap(vector<char> &chars, int nBegin, int nEnd)
{for(int i=nBegin; i<nEnd; i++) // 记住是 <nEnd
{if(chars[i] == chars[nEnd]) return false;
}
return true;
}
void Perm(vector<char> &chars, int k, int m)
{if(k==m)
{for(const char x:chars)
{cout<<x;}
cout<<endl;
}
else
{for(int i=k; i<=m; i++)
{if(IsSwap(chars, k, i))
{swap(chars[k], chars[i]);
Perm(chars, k+1, m);
swap(chars[k], chars[i]);
}
}
}
}
void Foo(vector<char> &chars)
{Perm(chars, 0, chars.size()-1);
}
// 字符串
bool IsSwap(string str, int nBegin, int nEnd)
{for(int i=nBegin; i<nEnd; i++) // 记住是 <nEnd
{if(str[i] == str[nEnd]) return false;
}
return true;
}
void Perm2(string str, int k, int m)
{if(k==m)
{
cout<<str;
cout<<endl;
}
else
{for(int i=k; i<=m; i++)
{if(IsSwap(str, k, i))
{swap(str[k], str[i]);
Perm2(str, k+1, m);
swap(str[k], str[i]);
}
}
}
}
void Foo2(string str)
{str.pop_back();
cout<<str<<endl;
Perm2(str, 0, str.length()-1);
}
int main()
{
// vector<char> chars;
// int n;
// cin>>n;
// char ele;
// for(int i=0; i<n; i++)
// {
// cin>>ele;
// chars.push_back(ele);
// }
// // for(const char x:chars) cout<<x;
// Foo(chars);
string str;
// scanf("%s", str); https://blog.csdn.net/liu16659/article/details/86772657 不倡议应用 scanf 输出 string 类型
cin>>str;
Foo2(str);
system("pause");
return 0;
}B. 疾速幂
// B. 疾速幂
#include<bits/stdc++.h>
using namespace std;
const long long Mod = 1e8 + 7;
typedef long long ll;
ll Pow(ll base, ll power)
{
ll result = 1;
for(int i=1; i<=power; ++i)
{
result *= power;
result %= 1000; // 每步后果提前进行取模
}
return result%1000;
}
// 疾速幂
// 所以咱们疾速幂算法的核心思想就是每一步都把指数分成两半，// 而相应的底数做平方运算。这样不仅能把十分大的指数给一直变小，// 所须要执行的循环次数也变小，而最初示意的后果却始终不会变
ll fastPow(ll base, ll power)
{
ll result = 1;
while(power>0)
{if(power%2 == 0)
{
base = base*base % Mod;
power /= 2;
}
else
{
power -= 1;
result = result*base % Mod;
base = base*base % Mod;
power /= 2;
}
}
return result;
}
ll myPow(int x)
{
ll result = 0;
for(int i=1; i<=x; ++i)
result += fastPow(i, i);
return (result+1)%Mod;
}
int main()
{
int x;
while(cin>>x)
{cout<<myPow(x)<<endl;
}
system("pause");
return 0;
}C. 求第 k 小的数
// C. 求第 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 n, k;
// cin>>n>>k;
// vector<int> vec;
// for(int i=0; i<n; ++i)
// {
// int num;
// scanf("%d", &num);
// vec.push_back(num);
// }
// sort(vec.begin(), vec.end());
// cout<<vec[k-1];
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:r]中的元素个数
if(k<=count) return RandomizedSelect(a, p, loc, k);
else return RandomizedSelect(a, loc+1, r, k-count);
}D. 外部收益率
// D. 外部收益率
#include<bits/stdc++.h>
using namespace std;
int main()
{int a[100], n;
while(scanf("%d", &n) && n)
{for(int i=0; i<=n; i++) scanf("%d", a+i);
double x = -1.0, y=1e6, irr, npv;
for(int j=0; j<200; j++)
{irr = (x+y)/2; // 枚举 irr 的取值范畴[-1.0, 1e6], 二分法迫近 (至于这个范畴怎么来的, 我就不分明了. 数学问题)
npv = 0;
for(int k=0; k<=n; k++)
npv += 1.0*a[k]/pow(1+irr, k);
if(fabs(npv)<1e-6) break; // 小于一个阈值, 认为就是方程的解
if(npv < 0) y = irr;
if(npv > 0) x = irr;
}
printf("%.2lf\n", irr);
memset(a, 0, sizeof(a)); // 每次重置 a 数组
}
// cout<<9/2.25<<endl;
system("pause");
return 0;
}E. 跳台阶
// 跳台阶
#include<bits/stdc++.h>
using namespace std;
// f(x) = f(x-1) + f(x-2)
int climbStairsMemo(int n, vector<int>& memo)
{if(memo[n]>0) return memo[n]; // 记录数组
if(n==1 || n==2) memo[n] = n;
else memo[n] = climbStairsMemo(n-1, memo) + climbStairsMemo(n-2, memo);
return memo[n];
}
int climbStairs(int n) {vector<int> memo(n+1, 0);
return climbStairsMemo(n, memo);
}
// 滚动数组 将空间复杂度由 O(n)优化成 O(1)
int climbStairs2(int n)
{
int p=0, q=0, r=1;
for(int i=1; i<=n; i++)
{
p = q;
q = r;
r = p+q;
}
return r;
}
int main()
{
int n;
cin>>n;
cout<<climbStairs2(n)%1000000007<<endl;
system("pause");
return 0;
}2.Contest2445 – 毕老师算法试验二
传送门在这里
题目总览:
A. 沙子的品质
// A. 沙子的品质 OJ 作业一 D 题
// 动静布局
#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f; // 为什么用 0x3f3f3f3f 而不必 0xffffff https://blog.csdn.net/jiange_zh/article/details/50198097
int Compute(int *nums, int n)
{int Sum[n+1]={0};
int DP[n+1][n+1]; // 之前用 DP[1005][1005], 导致栈空间溢出 https://blog.csdn.net/kangyupl/article/details/90723367
memset(DP, inf, sizeof(DP));
for(int i=1; i<=n; i++)
{Sum[i] = Sum[i-1] + nums[i];
DP[i][i] = 0;
}
for(int Len=2; Len<=n; Len++)
for(int left=1; left<=n-Len+1; left++)
{
int right = left+Len-1;
for(int k=left; k<right; k++)
{DP[left][right] = min(DP[left][k]+DP[k+1][right]+Sum[right]-Sum[left-1], DP[left][right]);
}
}
return DP[1][n];
}
int main()
{
int n;
cin>>n;
int nums[n+1];
nums[0] = 0;
for(int i=1; i<=n; ++i) cin>>nums[i];
cout<<Compute(nums, n)<<endl;
system("pause");
return 0;
}B. 最长公共子序列
// B. 最长公共子序列 OJ 作业一 F 题
// 动静布局
#include<bits/stdc++.h>
using namespace std;
int longestCommonSequence(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<<longestCommonSequence(a, b)<<endl;
system("pause");
return 0;
}C. 三角形的门路权
// C. 三角形最小门路权
// Leetcode 125 题
// 动静布局
#include<bits/stdc++.h>
using namespace std;
// 了解谬误, 直角三角形的状况.
int minimumTotal2(vector<vector<int>> &triangle)
{int n = triangle.size();
vector<vector<int>> dp(n, vector<int>(n));
dp[0][0] = triangle[0][0];
dp[1][0] = triangle[1][0], dp[1][1] = triangle[0][0]+triangle[1][1];
if(n==2) return dp[1][1];
for(int i=2; i<n; i++)
{dp[i][0] = dp[i-1][1] + triangle[i][0];
for(int j=1; j<=i-2; j++)
{dp[i][j] = max(dp[i-1][j-1], dp[i-1][j+1]) + triangle[i][j];
}
dp[i][i] = dp[i-1][i-1] + triangle[i][i];
dp[i][i-1] = dp[i-1][i-2] + triangle[i][i-1];
}
cout<<endl<<endl<<"DP 数组更新为:"<<endl;
for(const auto x:dp)
{for(const int y:x) cout<<y<<" ";
cout<<endl;
}
return *max_element(dp[n-1].begin(), dp[n-1].end());
}
// 看成等腰三角形
int maximumTotal(vector<vector<int>> &triangle)
{int n = triangle.size();
vector<vector<int>> dp(n, vector<int>(n,0));
dp[0][0] = triangle[0][0];
for(int i=1; i<n; i++)
{dp[i][0] = dp[i-1][0] + triangle[i][0];
for(int j=1; j<n-1; j++)
{dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
}
dp[i][i] = dp[i-1][i-1] + triangle[i][i];
}
return *max_element(dp[n-1].begin(), dp[n-1].end());
}
int main()
{
int n;
cin>>n;
vector<vector<int>> triangle(n, vector<int>(n));
for(int i=0; i<n; i++)
{for(int j=0; j<=i; j++)
cin>>triangle[i][j];
}
cout<<maximumTotal(triangle)<<endl;
system("pause");
return 0;
}D. 跳跃游戏Ⅱ
// D. 跳跃游戏Ⅱ
// LeetCode 第 45 题
// 贪婪算法
#include<bits/stdc++.h>
using namespace std;
// 思维就一句话：每次在上次能跳到的范畴（end）内抉择一个能跳的最远的地位（也就是能跳到 max_far 地位的点）作为下次的起跳点！int Jump(vector<int> &nums)
{int n = nums.size();
int max_far = 0; // 目前可能跳到的最远地位
int step = 0;
int end = 0; // 上次跳跃可达到的范畴右边界
for(int i=0; i<n-1; i++) //<n-1, 最初一个元素不必遍历.
{max_far = max(i+nums[i], max_far);
if(i == end)
{
end = max_far;
step++;
}
}
return step;
}
int main()
{
int n;
cin>>n;
vector<int> nums(n);
for(int i=0; i<n; i++) cin>>nums[i];
cout<<Jump(nums)<<endl;
system("pause");
return 0;
}E. 字母排序
// E. 字母排序
// 最长不降子序列
#include<bits/stdc++.h>
using namespace std;
// 1.LIS ---> LCS 最长递增子序列(排序 +LCS)
// const int N = 1010;
// int DP[N][N];
// int DIR[N][N];
// int LCS_Length(string a, string 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(string 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];
// }
// else if(DIR[i][j] == 2) LCS(a, i-1, j);
// else if(DIR[i][j] == 3) LCS(a, i, j-1);
// }
// string RD(string b, int &add) // 去重函数 hhh 变为 h
// {// bool Flag[b.size()] = {false};
// for(int i=1; i<b.size(); i++)
// {// if(b[i] == b[i-1])
// {
// add++;
// Flag[i] = true;
// }
// }
// for(int i=0; i<b.size(); i++)
// {// if(Flag[i] == 1) b[i] = '.';
// }
// // cout<<b<<endl;
// b.erase(std::remove(b.begin(), b.end(), '.'), b.end()); // 去重操作
// return b;
// }
// int LIS_Length(string a, string b)
// {// return LCS_Length(a, b);
// }
// int main()
// {
// string a, str;
// cin>>a;
// cin.ignore(); // 空格
// getline(cin, str);
// str += ' ';
// string b;
// int Start_pos = 0;
// int add = 0;
// for(int i=0; i<str.size(); i++)
// {// if(str[i] == ' ')
// {
// // cout<<"Flag"<<i<<endl;
// b = str.substr(Start_pos, i-Start_pos);
// // cout<<b<<endl;
// RD(b, add);
// cout<<LIS_Length(a, b)+add;
// Start_pos = i+1;
// add = 0;
// }
// }
// // string test;
// // cin>>test;
// // int add = 0;
// // cout<<RD(test, add)<<" "<<add<<endl;
// // cout<<test<<endl;
// system("pause");
// return 0;
// }
// 2.DP
// O(n^2)
// int LengthOfLIS(vector<int> &nums)
// {// int n = nums.size();
// if(n==0) return 0;
// vector<int> dp(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]);
// }
// }
// }
// return *max_element(dp.begin(), dp.end());
// }
// int main()
// {
// int n;
// while(scanf("%d", &n) && n)
// {// vector<int> nums(n);
// for(int i=0; i<n; i++) scanf("%d", &nums[i]);
// cout<<LengthOfLIS(nums)<<endl;
// }
// system("pause");
// return 0;
// }
// 3. 贪婪 + 二分查找
// 保护一个一维数组 B，并且这个数组是动静扩大的，初始大小为 1，//B[i]示意最长回升子序列长度是 i 的所有子串中开端最小的那个数，依据这个数字，咱们能够比拟晓得，// 只有以后考查的这个数比 B[i]大，那么以后这个数肯定能通过 B[i]形成一个长度为 i + 1 的回升子序列。// 如果以后考查的数并没有数组尾部的 B[i]大, 那么咱们抉择在 B 数组中找到第一个大于以后考查数的元素, 并且更换.
// 正确!!!
int BinarySearch(vector<int> &nums, int l, int r, int target) // 在 nums 数组中找到第一个大于 target 的数, 而后更新它
{if(l == r) return l;
int mid;
while(l <= r)
{mid = (l+r)/2;
if(nums[mid] == target) return mid; //return mid!
else if(nums[mid] > target) r = mid-1;
else l = mid+1;
}
return l;
}
int LengthOfLIS(vector<int> &nums)
{int n = nums.size();
vector<int> B(n+1);
B[0] = 0;
B[1] = nums[0];
int len = 1; // 示意 B 数组的长度
for(int i=1; i<n; i++)
{if(nums[i] > B[len])
{B[++len] = nums[i];
}
else if(nums[i] < B[len])
{int pos = BinarySearch(B, 1, len, nums[i]); // 在 B 数组中找到第一个大于 nums[i]的元素地位
cout<<pos<<""<<i<<" "<<nums[i]<<endl;
B[pos] = nums[i];
}
}
for(const int x:B) cout<<x<<" ";
cout<<endl;
return len;
}
// 力扣! https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti/
// 思考一个简略的贪婪，如果咱们要使回升子序列尽可能的长，则咱们须要让序列回升得尽可能慢，因而咱们心愿每次在回升子序列最初加上的那个数尽可能的小。// 咱们顺次遍历数组 nums 中的每个元素，并更新数组 d 和 len 的值。如果 nums[j] > d[len] 则更新 len = len + 1
// 否则在 d[1...len] 中 找到 d[i-1] < nums[j] < d[i]的 pos 值, 而后更新 d[i] = nums[j]
int lengthOfLIS(vector<int> &nums)
{int len = 1, n = int(nums.size());
if(n == 0) return 0;
vector<int> d(n+1, 0);
d[len] = nums[0];
for(int i=1; i<n; ++i)
{if(nums[i] > d[len])
d[++len] = nums[i];
else
{int l = 1, r = len, pos = 0; // 如果找不到阐明所有的数都比 nums[i]大, 此时要更新 d[1]
while(l <= r)
{int mid = (l+r) >> 1;
if(d[mid] < nums[i])
{
pos = mid;
l = mid+1;
}
else r = mid-1;
}
d[pos+1] = nums[i];
}
}
return len;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
vector<int> nums(n);
for(int i=0; i<n; i++)
cin>>nums[i];
cout<<LengthOfLIS(nums)<<endl;
}
system("pause");
return 0;
}3.Contest2453 – 毕老师算法试验三
传送门在这里
题目总览:
A.Homework
// 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;
}B. 区间蕴含问题
// 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;
}C. 最长子序列
// 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;
}D. 三值排序
// D. 三值排序
#include<bits/stdc++.h>
using namespace std;
int ThreeSort(vector<int> &nums)
{int n = nums.size();
int a=0, b=0, c=0;
for(int i=0; i<n; ++i)
{if(nums[i]==1) a++;
else if(nums[i]==2) b++;
else if(nums[i]==3) c++;
}
int dif[4][4] = {0};
for(int i=0; i<a; i++)
if(nums[i] != 1) dif[1][nums[i]]++;
for(int i=a; i<a+b; i++)
if(nums[i] != 2) dif[2][nums[i]]++;
for(int i=a+b; i<n; i++)
if(nums[i] != 3) dif[3][nums[i]]++;
int ans = 0, sum = 0;
for(int i=1; i<4; i++)
{for(int j=i+1; j<4; j++)
{if(dif[i][j] <= dif[j][i])
{ans += dif[i][j];
sum += dif[j][i] - dif[i][j];
}
else
{ans += dif[j][i];
sum += dif[i][j] - dif[j][i];
}
}
}
ans = ans + sum/3*2; // 三个数字都不在本人该在的地位，然而只须要两步就能变得有序：213 变为 123 只需两步 312 132 等等同样
return ans;
}
int main()
{
int n;
cin>>n;
vector<int> nums(n);
int a=0, b=0, c=0;
for(int i=0; i<n; ++i)
scanf("%d", &nums[i]);
cout<<ThreeSort(nums)<<endl;
system("pause");
return 0;
}E. 法师康的工人
// E. 法师康的工人
// 这一题有点问题, 我如同没改过来
#include<bits/stdc++.h>
using namespace std;
bool cmp(pair<int, int> a, pair<int, int> b)
{return a.second < b.second;}
int main()
{
int n;
cin>>n;
vector<pair<int, int>> vec;
int left, right;
for(int i=0; i<n; ++i)
{scanf("%d%d", &left, &right);
vec.push_back(pair<int, int>(left, right));
}
sort(vec.begin(), vec.end(), cmp);
int left_border = vec[0].first;
int right_border = vec[0].second;
int max_ContinuousLength = right_border-left_border;
int max_IntervalLength = 0;
for(int i=1; i<n; ++i)
{if(vec[i].first <= right_border)
{right_border = max(right_border, vec[i].second);
left_border = min(left_border, vec[i].first);
}
else
{max_ContinuousLength = max(max_ContinuousLength, right_border-left_border);
max_IntervalLength = max(max_IntervalLength, vec[i].first-right_border);
left_border = vec[i].first; // 呈现距离, 重置边界
right_border = vec[i].second;
}
}
max_ContinuousLength = max(max_ContinuousLength, right_border-left_border);
// 避免 2 (100 500) (400 900)这种没有间断的状况呈现, 间接跳出循环的话
cout<<max_ContinuousLength<<" "<<max_IntervalLength<<endl;
system("pause");
return 0;
}
// 10
// 2 3
// 4 5
// 6 7
// 8 9
// 10 11
// 12 13
// 14 15
// 16 17
// 18 19
// 1 20
// 19 1
// 请按任意键持续. . .
// 正确答案:19 0 谬误的起因? 咋改4.Contest2462 – 毕老师算法试验四
传送门在这里
题目总览:
A. 凯撒加密法
// A.żČöĂÜÂë
#include<bits/stdc++.h>
using namespace std;
string CaesarCipher(string ciphertext, int n)
{int length = ciphertext.size();
for(int i=0; i<length; ++i)
{if(isupper(ciphertext[i]))
ciphertext[i] = 'A' + (ciphertext[i]-'A'-n+26)%26;
else if(islower(ciphertext[i]))
ciphertext[i] = 'a' + (ciphertext[i]-'a'-n+26)%26;
}
return ciphertext;
}
int main()
{
int T;
scanf("%d", &T);
// for(int i=0; i<T; ++i)
// {
// string ciphertext;
// // cin>>ciphertext;
// cin.ignore();
// getline(cin, ciphertext);
// int k;
// cin>>k;
// k = k%26;
// cout<<CaesarCipher(ciphertext, k)<<endl;
// }
string str[T];
int change[T];
for(int i=0; i<T; ++i)
{cin>>str[i];
cin>>change[i];
change[i] %= 26;
}
for(int i=0; i<T; i++)
{cout<<CaesarCipher(str[i], change[i])<<endl;
}
system("pause");
return 0;
}B. 维吉尼亚明码
// B.¸ĽźŞÄáŃÇĂÜÂë
#include<bits/stdc++.h>
using namespace std;
string fill(string key, string plainText)
{int len1 = key.size();
int len2 = plainText.size();
if(len1 < len2)
{
int num = len2 - len1;
string temp = key;
for(int i=0; i<num; ++i)
{key += temp[i%len1];
}
}
for(int i=0; i<len2; ++i)
{if(islower(key[i]))
key[i] -= 32;
}
return key;
}
int main()
{
string key, cipherText;
cin>>key>>cipherText;
key = fill(key, cipherText);
// cout<<key<<endl;
int len = cipherText.size();
string plainText;
int change;
for(int i=0; i<len; ++i)
{change = key[i] - 'A';
// cout<<i<<":"<<change<<endl;
if(isupper(cipherText[i]))
plainText.push_back('A' + (cipherText[i]-'A'- change + 26)%26);
else
plainText.push_back('a' + (cipherText[i]-'a'- change + 26)%26);
}
cout<<plainText<<endl;
system("pause");
return 0;
}C. 简略的明码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
int f[35] = {0, 0, 0, 1};
for(int i=4; i<=30; ++i)
f[i] = f[i-1]*2 + pow(2, i-4) - f[i-4];
while(cin>>n && n>=1 && n<=30)
cout<<f[n]<<endl;
system("pause");
return 0;
}D. 乏味的素数
// 带佬代码
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int n,ans,last;
bool visited[32];
bool isPrime[40]={0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0};
void pc(int cur)
{if(cur == n && isPrime[1+last])
{
ans++;
return;
}
for(int i = 2; i <= n; i++)
{if(!visited[i] && isPrime[last+i])
{
int t = last;
last = i;
visited[i] = true;
pc(cur+1);
visited[i] = false;
last = t;
}
}
}
int main()
{while(~scanf("%d",&n))
{memset(visited,0,sizeof(visited));
ans = 0;
last = 1;
pc(1);
printf("%d\n",ans);
}
return 0;
}E. 数据加密
// E. 数据加密
#include<bits/stdc++.h>
using namespace std;
string CipherCompute(string PlainText)
{int n = PlainText.size();
string ans;
if(n==0) return {};
if(n==1) return PlainText;
int left = 0, right = n-1;
while(n>0)
{if(PlainText[left] < PlainText[right])
{ans += PlainText[left];
left++;
n--;
}
else if(PlainText[left] > PlainText[right])
{ans += PlainText[right];
right--;
n--;
}
else
{
int temp_left = left+1, temp_right = right-1;
while(temp_left<n && temp_right>=0 && temp_left <= temp_right && PlainText[temp_left] == PlainText[temp_right])
{
temp_left++;
temp_right--;
}
if(PlainText[temp_left]>PlainText[temp_right])
{ans += PlainText[right];
right--;
n--;
}
else
{ans += PlainText[left];
left++;
n--;
}
}
}
return ans;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
string PlainText;
cin>>PlainText;
string Cipher = CipherCompute(PlainText);
cout<<Cipher<<endl;
}
system("pause");
return 0;
}
// 带佬代码
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int main()
{
int n;
char str[2005],ans[2005];
while(~scanf("%d",&n))
{scanf("%s",str);
int i = 0,j = n-1;
while(i <= j)
{
bool flag = false;
for(int k = 0; i+k < j-k; k++)
{if(str[i+k] < str[j-k])
{
flag = true;
break;
}
if(str[i+k] > str[j-k]) break;
}
if(flag) printf("%c",str[i++]);
else printf("%c",str[j--]);
}
printf("\n");
}
return 0;
}(～~▽~)～
如果大家感觉本篇文章对本人有所帮忙的话, 无妨去我的集体博客 — 乔治的编程小屋逛逛吧.
正文完
