https://ac.nowcoder.com/acm/contest/5670#question
D. Drop Voicing
题意：给一个1~n的排列，执行以下两种操作，将序列变为升序的，连续相同的操作称为一组，问最少执行多少组操作一
操作一：将当前序列中倒数第二个数移到第一个
操作二：将第一个数移到最后
思路：把整个序列看作一个圆盘，圆盘上有个指针，初始时指针指向最后一个数，操作一相当于改变指针所指数的位置，操作二相当于改变指针的位置，求出圆盘上的LIS，通过操作一移动其他数，其他数的个数即需要多少组操作一
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 5;
int p[N], dp[N];
int main()
{
int n;
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%d", &p[i]);
p[i + n] = p[i];
}
int maxx = 0;
for(int l = 1; l <= n; ++l) {
int r = l + n - 1;
memset(dp, 0, sizeof(dp));
for(int i = l; i <= r; ++i) {
dp[i] = 1;
for(int j = l; j < i; ++j) {
if(p[j] < p[i])
dp[i] = max(dp[i], dp[j] + 1);
}
maxx = max(maxx, dp[i]);
}
}
cout<<n - maxx<<'\n';
return 0;
}
E. Bogo Sort
题意：Tonnnny写了个排序的函数，这个函数有问题，只能将某些序列排好序，给出初始置换序列，问有多少种排列通过该函数能够排好序
思路：求置换的循环节长度，对每个数求循环节，整个置换的循环节长度即为所有数循环节长度的lcm
python:
import math
N = 100007
vis = [0] * N
def gcd(a, b):
if b > 0:
return gcd(b, a % b)
else:
return a
n = int(input())
p = list(map(int, input().split()))
ans = 1
for i in range(n):
p[i] = p[i] - 1
for i in range(n):
tmp = 0
pos = i
while vis[pos] == 0:
vis[pos] = 1
tmp = tmp + 1
pos = p[pos]
if tmp > 0:
ans = ans // gcd(ans, tmp) * tmp
print(ans)
c++大数
#include <bits/stdc++.h>
#pragma GCC optimize(3)
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
typedef unsigned long long ll;
const int N = 1e5 + 10;
int p[N];
bool vis[N];
//大数
struct BigInteger
{
static const int BASE = 100000000; //和WIDTH保持一致
static const int WIDTH = 8; //八位一存储,如修改记得修改输出中的%08d
bool sign; //符号, 0表示负数
size_t length; //位数
vector<int> num; //反序存
//构造函数
BigInteger(long long x = 0)
{
*this = x;
}
BigInteger(const string &x)
{
*this = x;
}
BigInteger(const BigInteger &x)
{
*this = x;
}
//剪掉前导0，并且求一下数的位数
void cutLeadingZero()
{
while (num.back() == 0 && num.size() != 1)
{
num.pop_back();
}
int tmp = num.back();
if (tmp == 0)
{
length = 1;
}
else
{
length = (num.size() - 1) * WIDTH;
while (tmp > 0)
{
length++;
tmp /= 10;
}
}
}
//赋值运算符
BigInteger &operator=(long long x)
{
num.clear();
if (x >= 0)
{
sign = true;
}
else
{
sign = false;
x = -x;
}
do
{
num.push_back(x % BASE);
x /= BASE;
}
while (x > 0);
cutLeadingZero();
return *this;
}
BigInteger &operator=(const string &str)
{
num.clear();
sign = (str[0] != '-'); //设置符号
int x, len = (str.size() - 1 - (!sign)) / WIDTH + 1;
for (int i = 0; i < len; i++)
{
int End = str.size() - i * WIDTH;
int start = max((int)(!sign), End - WIDTH); //防止越界
sscanf(str.substr(start, End - start).c_str(), "%d", &x);
num.push_back(x);
}
cutLeadingZero();
return *this;
}
BigInteger &operator=(const BigInteger &tmp)
{
num = tmp.num;
sign = tmp.sign;
length = tmp.length;
return *this;
}
//绝对值
BigInteger abs() const
{
BigInteger ans(*this);
ans.sign = true;
return ans;
}
//正号
const BigInteger &operator+() const
{
return *this;
}
//负号
BigInteger operator-() const
{
BigInteger ans(*this);
if (ans != 0)
ans.sign = !ans.sign;
return ans;
}
// + 运算符
BigInteger operator+(const BigInteger &b) const
{
if (!b.sign)
{
return *this - (-b);
}
if (!sign)
{
return b - (-*this);
}
BigInteger ans;
ans.num.clear();
for (int i = 0, g = 0;; i++)
{
if (g == 0 && i >= num.size() && i >= b.num.size())
break;
int x = g;
if (i < num.size())
x += num[i];
if (i < b.num.size())
x += b.num[i];
ans.num.push_back(x % BASE);
g = x / BASE;
}
ans.cutLeadingZero();
return ans;
}
// - 运算符
BigInteger operator-(const BigInteger &b) const
{
if (!b.sign)
{
return *this + (-b);
}
if (!sign)
{
return -((-*this) + b);
}
if (*this < b)
{
return -(b - *this);
}
BigInteger ans;
ans.num.clear();
for (int i = 0, g = 0;; i++)
{
if (g == 0 && i >= num.size() && i >= b.num.size())
break;
int x = g;
g = 0;
if (i < num.size())
x += num[i];
if (i < b.num.size())
x -= b.num[i];
if (x < 0)
{
x += BASE;
g = -1;
}
ans.num.push_back(x);
}
ans.cutLeadingZero();
return ans;
}
// * 运算符
BigInteger operator*(const BigInteger &b) const
{
int lena = num.size(), lenb = b.num.size();
BigInteger ans;
for (int i = 0; i < lena + lenb; i++)
ans.num.push_back(0);
for (int i = 0, g = 0; i < lena; i++)
{
g = 0;
for (int j = 0; j < lenb; j++)
{
long long x = ans.num[i + j];
x += (long long)num[i] * (long long)b.num[j];
ans.num[i + j] = x % BASE;
g = x / BASE;
ans.num[i + j + 1] += g;
}
}
ans.cutLeadingZero();
ans.sign = (ans.length == 1 && ans.num[0] == 0) || (sign == b.sign);
return ans;
}
//*10^n 大数除大数中用到
BigInteger e(size_t n) const
{
int tmp = n % WIDTH;
BigInteger ans;
ans.length = n + 1;
n /= WIDTH;
while (ans.num.size() <= n)
ans.num.push_back(0);
ans.num[n] = 1;
while (tmp--)
ans.num[n] *= 10;
return ans * (*this);
}
// /运算符 (大数除大数)
BigInteger operator/(const BigInteger &b) const
{
BigInteger aa((*this).abs());
BigInteger bb(b.abs());
if (aa < bb)
return 0;
char *str = new char[aa.length + 1];
memset(str, 0, sizeof(char) * (aa.length + 1));
BigInteger tmp;
int lena = aa.length, lenb = bb.length;
for (int i = 0; i <= lena - lenb; i++)
{
tmp = bb.e(lena - lenb - i);
while (aa >= tmp)
{
str[i]++;
aa = aa - tmp;
}
str[i] += '0';
}
BigInteger ans(str);
delete[] str;
ans.sign = (ans == 0 || sign == b.sign);
return ans;
}
// %运算符
BigInteger operator%(const BigInteger &b) const
{
return *this - *this / b * b;
}
// ++ 运算符
BigInteger &operator++()
{
*this = *this + 1;
return *this;
}
// -- 运算符
BigInteger &operator--()
{
*this = *this - 1;
return *this;
}
// += 运算符
BigInteger &operator+=(const BigInteger &b)
{
*this = *this + b;
return *this;
}
// -= 运算符
BigInteger &operator-=(const BigInteger &b)
{
*this = *this - b;
return *this;
}
// *=运算符
BigInteger &operator*=(const BigInteger &b)
{
*this = *this * b;
return *this;
}
// /= 运算符
BigInteger &operator/=(const BigInteger &b)
{
*this = *this / b;
return *this;
}
// %=运算符
BigInteger &operator%=(const BigInteger &b)
{
*this = *this % b;
return *this;
}
// < 运算符
bool operator<(const BigInteger &b) const
{
if (sign != b.sign) //正负，负正
{
return !sign;
}
else if (!sign && !b.sign) //负负
{
return -b < -*this;
}
//正正
if (num.size() != b.num.size())
return num.size() < b.num.size();
for (int i = num.size() - 1; i >= 0; i--)
if (num[i] != b.num[i])
return num[i] < b.num[i];
return false;
}
bool operator>(const BigInteger &b) const
{
return b < *this; // > 运算符
}
bool operator<=(const BigInteger &b) const
{
return !(b < *this); // <= 运算符
}
bool operator>=(const BigInteger &b) const
{
return !(*this < b); // >= 运算符
}
bool operator!=(const BigInteger &b) const
{
return b < *this || *this < b; // != 运算符
}
bool operator==(const BigInteger &b) const
{
return !(b < *this) && !(*this < b); //==运算符
}
// 逻辑运算符
bool operator||(const BigInteger &b) const
{
return *this != 0 || b != 0; // || 运算符
}
bool operator&&(const BigInteger &b) const
{
return *this != 0 && b != 0; // && 运算符
}
bool operator!()
{
return (bool)(*this == 0); // ！ 运算符
}
//重载<<使得可以直接输出大数
friend ostream &operator<<(ostream &out, const BigInteger &x)
{
if (!x.sign)
out << '-';
out << x.num.back();
for (int i = x.num.size() - 2; i >= 0; i--)
{
char buf[10];
//如WIDTH和BASR有变化,此处要修改为%0(WIDTH)d
sprintf(buf, "%08d", x.num[i]);
for (int j = 0; j < strlen(buf); j++)
out << buf[j];
}
return out;
}
//重载>>使得可以直接输入大数
friend istream &operator>>(istream &in, BigInteger &x)
{
string str;
in >> str;
size_t len = str.size();
int start = 0;
if (str[0] == '-')
start = 1;
if (str[start] == '\0')
return in;
for (int i = start; i < len; i++)
{
if (str[i] < '0' || str[i] > '9')
return in;
}
x.sign = !start;
x = str.c_str();
return in;
}
};
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while(!isdigit(ch)) {
if(ch == '-')
f = -1;
ch = getchar();
}
while(isdigit(ch)) {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
BigInteger gcd(BigInteger a, BigInteger b) {
return (b > 0) ? gcd(b, a % b) : a;
}
int main()
{
int n;
n = read();
for(int i = 1; i <= n; ++i)
p[i] = read();
BigInteger ans = 1;
int pos;
for(int i = 0; i <= n; ++i) vis[i] = 0;
for(int i = 1; i <= n; ++i) {
BigInteger tmp = 0;
pos = i;
while(!vis[pos]) {
tmp += 1;
vis[pos] = 1;
pos = p[pos];
}
if(tmp > 0)
ans = ans / gcd(ans, tmp) * tmp;
}
cout<<ans<<'\n';
return 0;
}
F. DPS
签到~~~ 注意向上取整
#include <bits/stdc++.h>
#pragma GCC optimize(3)
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
typedef long long ll;
const int N = 110;
int d[N];
int main()
{
int n, maxx = 0;
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%d", &d[i]);
maxx = max(maxx, d[i]);
}
for(int i = 1; i <= n; ++i) {
int s = (int)ceil(50.0 / maxx * d[i]);
cout<<'+';
for(int j = 1; j <= s; ++j)
cout<<'-';
cout<<'+'<<'\n';
cout<<'|';
for(int j = 1; j <= s; ++j) {
if(j == s && d[i] == maxx)
cout<<'*';
else
cout<<' ';
}
cout<<'|'<<d[i]<<'\n';
cout<<'+';
for(int j = 1; j <= s; ++j)
cout<<'-';
cout<<'+'<<'\n';
}
return 0;
}
I. Hard Math Problem
题意：有一个无穷大的二维网格，每个格子可以是1、2或者3，每个1旁边要有一个2和3，使1的占比最大，求最大比值
思路：一个2最多与4个1相邻，一个3也最多与4个1相邻，设1的个数是x，那么总个数是x + x / 4 + x / 4 = 3x / 2，比值是2 / 3
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 110;
int main()
{
double a = 2.0 / 3.0;
printf("%.6f\n", a);
return 0;
}
京公网安备 11010502036488号