[toc]
第一题 卡片
简单模拟就好了
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N=1e5+10;
typedef long long ll;
ll a[N];
int b[N];
bool check(int x)
{
vector<int> a(10);
while(x)
{
a[x%10]++;
x/=10;
}
for(int i=0;i<=9;i++)
if(b[i]<a[i])
{
return false;
}
else
b[i]-=a[i];
return true;
}
int main()
{
for(int i=0;i<=9;i++)
b[i]=2021;
int i=1;
while(1)
{
if(!check(i))
break;
i++;
}
cout<<i-1<<endl;
return 0;
}
第二题 直线
wa了,不能直接用double去存截距,因为浮点数有精度问题
斜率问题需要考虑
- 降低精度
- 考虑斜率无穷大
对于截距y = kx + d,d = y - kx
由于加减法的误差很大,所以需要转化为乘除法。
d = y1 - (y1 - y2)/(x1 - x2) * x1
= d = (x1y2 - y1x2)/(x1-x2)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
const double eps = 1e-18;
int cmp(double a, double b)
{
if (abs(a - b) < eps)
return 0;
if (a < b) return -1;
else return 1;
}
struct node
{
double k;
double d;
bool operator < (const node b) const
{
if (cmp(k, b.k) != 0)
return k < b.k;
return d < b.d;
}
bool operator == (const node b)const
{
if (cmp(d, b.d) == 0 && cmp(k, b.k) == 0)
return true;
return false;
}
};
set<node> s;
int gcd(int a, int b)
{
if (!b) return a;
return gcd(b, a % b);
}
int main()
{
int n, m;
n = 20, m = 21;
for(int i=0;i<n;i++)
for (int j = 0;j < m;j++)
{
for (int x = 0;x < n;x++)
for (int y = 0;y < m;y++)
{
if (x == i || y == j) continue; //考虑斜率无穷大和共点的情况
double k = 0;
double d = 0;
k =(double) (y - j) / (x - i);
d = (double)(x * j - i * y) / (x - i); //减小误差
node t = { k,d };
s.insert(t);
}
}
cout << s.size()+n+m;
return 0;
}
第三题货物摆放
筛质数,然后用质数分解质因数,求出所有约数
求出所有约数枚举每三个约数是否x*y*z = n
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
typedef pair<ll, ll> PII;
PII d[N];
ll f[N];
int fcnt;
bool st[N];
int cnt, primes[N];
int dcnt;
void get_primes(ll x)
{
for (int i = 2;i <= x;i++)
{
if (!st[i])
primes[cnt++] = i;
for (int j = 0;1ll*primes[j] * i <= x;i++)
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
void divide(ll x)
{
for (int i = 0;i < cnt;i++)
{
if (primes[i] > x) break;
int p = primes[i];
if (x % p == 0)
{
int s = 0;
while (x % p == 0) s++, x /= p;
d[dcnt++] = { p,s};
}
}
if (x > 1)
d[dcnt++] = { x,1 };
}
void dfs(int u, ll sum)
{
if (u >= dcnt) {
f[fcnt++] = sum;
return;
}
ll p = d[u].first;
ll time = d[u].second;
for (int i = 0;i <= time;i++)
{
dfs(u + 1, sum);
sum = sum * p;
}
}
int main()
{
get_primes(N - 1);
ll n = 2021041820210418;
ll cnt = 0;
divide(n);
dfs(0,1);
for (ll i = 0;i < fcnt;i++)
{
ll x = f[i];
for (ll j = 0;j < fcnt;j++)
{
ll y = f[j];
if ((n / x) % y != 0) continue;
for (ll k = 0;k < fcnt;k++)
{
ll z = f[k];
if (n / x / y == z) {
cnt++;
}
}
}
}
cout << cnt << endl;
return 0;
}
第四题 路径
走一遍最短路就可以了
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 3000 + 10;
int dist[N];
int w[N][N];
bool vis[N];
int st = 1;
int ed = 2021;
int dijkstra(int st)
{
queue<int> q;
q.push(st);
dist[st] = 0;
for (int i = 0;i < ed;i++)
{
int minn = 0x3f3f3f3f;
int v = 0;
for(int j=1;j<=ed;j++)
if (!vis[j] && minn > dist[j])
{
minn = dist[j];
v = j;
}
vis[v] = true;
for (int j = 1;j <= ed;j++)
dist[j] = min(dist[j], dist[v] + w[v][j]);
}
return dist[ed];
}
int gcd(int a, int b)
{
if (!b) return a;
return gcd(b, a % b);
}
int main()
{
memset(dist, 0x3f, sizeof dist);
memset(w, 0x3f, sizeof w);
for(int i=1;i<=ed;i++)
for (int j = 1;j <= ed;j++)
{
if (abs(i - j) > 21) continue;
w[i][j] = min(1ll*w[i][j],1ll * i * j / gcd(i, j));
w[j][i] = min(1ll * w[j][i], 1ll * i * j / gcd(i, j));
}
cout << dijkstra(st) << endl;
return 0;
}
第五题 空间
签到成功
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 3000 + 10;
int dist[N];
int w[N][N];
bool vis[N];
int st = 1;
int ed = 2021;
int dijkstra(int st)
{
queue<int> q;
q.push(st);
dist[st] = 0;
for (int i = 0;i < ed;i++)
{
int minn = 0x3f3f3f3f;
int v = 0;
for(int j=1;j<=ed;j++)
if (!vis[j] && minn > dist[j])
{
minn = dist[j];
v = j;
}
vis[v] = true;
for (int j = 1;j <= ed;j++)
dist[j] = min(dist[j], dist[v] + w[v][j]);
}
return dist[ed];
}
int gcd(int a, int b)
{
if (!b) return a;
return gcd(b, a % b);
}
int main()
{
ll ed = 256ll * 1024 * 1024;
ll res = ed / 4;
cout << res << endl;
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 3000 + 10;
int dist[N];
int w[N][N];
bool vis[N];
int st = 1;
int ed = 2021;
int dijkstra(int st)
{
queue<int> q;
q.push(st);
dist[st] = 0;
for (int i = 0;i < ed;i++)
{
int minn = 0x3f3f3f3f;
int v = 0;
for(int j=1;j<=ed;j++)
if (!vis[j] && minn > dist[j])
{
minn = dist[j];
v = j;
}
vis[v] = true;
for (int j = 1;j <= ed;j++)
dist[j] = min(dist[j], dist[v] + w[v][j]);
}
return dist[ed];
}
int gcd(int a, int b)
{
if (!b) return a;
return gcd(b, a % b);
}
int main()
{
ll ed = 256ll * 1024 * 1024;
ll res = ed / 4;
cout << res << endl;
return 0;
}
第六题 时间显示
模拟题
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
void solve()
{
ll n;
cin >> n;
n %= (24 * 60 * 60*1000);
n /= 1000; //舍弃毫秒
int hour = n / 3600;
int min = n / 60 % 60;
int second = n % 60;
printf("%02d:%02d:%02d\n", hour, min, second);
}
int main()
{
int t;
t=1;
while (t--)
solve();
return 0;
}
第七题 砝码称重
dp题,分析如下
题解
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
bool dp[105][N];
int w[N];
int main()
{
int n;
cin >> n;
int m = 0;
for (int i = 1;i <= n;i++)
cin >> w[i], m += w[i];
dp[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
{
dp[i][j]|=dp[i-1][j];
dp[i][j]|=dp[i-1][abs(j-w[i])];
dp[i][j]|=dp[i-1][j+w[i]];
}
int res=0;
for(int i=1;i<=m;i++)
res+=dp[n][i];
cout<<res<<endl;
return 0;
}
第八题 杨辉三角形
暴力的优化或者二分
题解
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll res = 1e18;
ll n;
ll check(ll a, ll b)
{//a表示行,b表示列
ll res = 1;
for (int l = 1, r = a;l <= b;l++,r--)
{
res = res * r / l;
if (res > n) break;
}
return res;
}
void deal(int k)
{//二分枚举行
int l = k, r = 1e9;
while (l < r)
{
int mid = l + r >> 1;
if (check(mid, k) >= n)
r = mid;
else
l = mid + 1;
}
if (check(l, k) == n)
res = min(res, 1ll*l*(l+1)/2 + k + 1);
}
void solve()
{
cin >> n;
res = 1e18;
for (int k = 16;k;k--)
deal(k); //枚举列
if(n == 1) res = 1; //1比较特殊,在第0列
cout << res << endl;
}
int main()
{
int t;
t = 1;
while (t--)
solve();
return 0;
}
第九题 双向排序
只会暴力
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int a[N];
bool cmp(int &a,int &b)
{
return a>b;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
a[i]=i;
while(m--)
{
int p,k;
cin>>p>>k;
if(p==0){
sort(a+1,a+1+k,cmp);
}
else
sort(a+k,a+1+n);
}
for(int i=1;i<=n;i++)
cout<<a[i]<<' ';
return 0;
}
第十题 括号序列
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5000+10;
const int mod = 1e9+7;
char s[N];
int n;
int dp[N][N];
typedef long long ll;
ll cal()
{
memset(dp,0,sizeof dp);
dp[0][0]=1;
for(int i=1;i<=n;i++)
if(s[i] == '(')
{
//dp[i-1][-1]不是合法的方案,因此不能转移
for(int j=1;j<=n;j++)
dp[i][j] = dp[i-1][j-1];
}
else
{
dp[i][0] = (dp[i-1][0] + dp[i-1][1])%mod;
for(int j=1;j<=n;j++)
dp[i][j] = (dp[i][j-1] + dp[i-1][j+1])%mod;
}
for(int i=0;i<=n;i++)
if(dp[n][i])
return dp[n][i];
}
int main()
{
cin>>s + 1;
n = strlen(s+1);
ll l = cal();
//通过翻转,可以避免重复
reverse(s+1,s+1+n);
for(int i=1;i<=n;i++)
if(s[i] == '(') s[i]=')';
else s[i]='(';
ll r = cal();
cout<<1ll*l*r % mod<<endl;
return 0;
}
