【T1】出租
签到题，没什么考点，第二个数组找第一个数组的下标就好
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<set>
#include<map>
#include<vector>
#define ft first
#define sd second
#define js std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
//int d[N], e[N], ne[N], w[N], h[N], idx;
//int dir[4][2] = {{1,0},{0,-1},{-1,0},{0,1}};
//priority_queue<int, vector<int>, greater<int>> r;
const int N = 100010;
const int INF = 0x3f3f3f3f;
int m, t, k;
int n, a[N], q[N];
int number[10], id[10];
int cntarr, cntindex = 11;
string s;
int main()
{
js;
cin >> s;
int len = s.size();
for(int i = 0; i < len; i++)
{
if(!number[s[i]-'0'])
{
number[s[i]-'0'] = 1;
cntarr ++;
}
}
int cnt = 1;
// cout << "*" << cntarr << ' ';
cout << "int[] arr = new int[]{";
for(int i = 9; i >= 0; i--)
if(number[i])
{
if(cntarr > 1)
cout << i << ',';
else cout << i << "};\n";
cntarr --;
id[cnt++] = i;
}
cout << "int[] index = new int[]{";
for(int i = 0; i < len; i++)
{
for(int j = 1; j < cnt; j++)
{
if(id[j] == s[i]-'0')
{
if(i != len-1) cout << j-1 << ',';
else cout << j-1 << "};";
}
}
}
// for(int i = 1; i < cnt; i++)
// cout << id[i] << ' ';
return 0;
}
【T2】最长连续递增子序列
【考点】没什么考点，顶多算是双指针吧
（第一眼以为DP存LIS（最长递增子序列），没敢开，写完一道之后发现不少人写，才发现题目让找的子序列是连续的）
双指针写，维护最长区间的开头结尾即可(注意输出格式！)
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<set>
#include<map>
#include<vector>
#define ft first
#define sd second
#define js std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
//int d[N], e[N], ne[N], w[N], h[N], idx;
//int dir[4][2] = {{1,0},{0,-1},{-1,0},{0,1}};
//priority_queue<int, vector<int>, greater<int>> r;
const int N = 100010;
const int INF = 0x3f3f3f3f;
int m, t, k;
int n, a[N], q[N];
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
t = a[1];
int ansl = 0, ansr = 0, maxlen = 0;
for(int i = 2; i <= n; i++)
{
int cnt = 0, l = i, r = i;
while(a[i] > t && i <= n)
{
cnt += 1;
t = a[i];
i++;
r = i;
}
// cout << "**" << cnt << ' ';
// cout << '\n';
if(cnt > maxlen)
{
ansl = l, ansr = r;
maxlen = cnt;
}
t = a[i];
}
// cout << ansl << ' ' << ansr << '\n';
if(ansl == ansr) cout << a[1];
else
for(int i = ansl-1; i < ansr; i++)
if(i != ansr-1)cout << a[i] << ' ';
else cout << a[i];
return 0;
}
【T3】那就别担心了
【考点】DFS或BFS，有向图
统计哪些点能走到结尾即可；考场上差一个bug，结束后5min修了一下，应该是没问题了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1010;
int n, m, a, b;
int e[N],v[N], flag;
vector<int> vec[N];
queue<int> r;
void bfs(int a)
{
r.push(a);
v[a]=1; e[a]=1;
while(r.size())
{
int t = r.front(); r.pop();
v[t] = 0;
if(t == b) continue;
for(int i = 0; i < vec[t].size(); i++) // 寻找该点的每一个儿子
{
int tt = vec[t][i];
e[tt] += e[t];
if(!v[tt]) r.push(tt), v[tt]=1;
}
e[t] = 0;
if(!vec[t].size()) flag = 1;
}
return ;
}
int main()
{
scanf("%d%d",&n,&m);
while(m--)
{
scanf("%d%d",&a,&b);
vec[a].push_back(b);
}
scanf("%d%d",&a,&b);
bfs(a);
printf("%d ", e[b]);
if(flag) printf("No\n");
else printf("Yes\n");
return 0;
}
【T4】推断学生所属学校的人数）
【考点】并查集（保存名字有些复杂，但是数据很小，O（n^2）查找就行）
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<set>
#include<map>
#include<vector>
#define ft first
#define sd second
#define js std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long LL;
typedef pair<string, int> PII;
//int d[N], e[N], ne[N], w[N], h[N], idx;
//int dir[4][2] = {{1,0},{0,-1},{-1,0},{0,1}};
//priority_queue<int, vector<int>, greater<int>> r;
const int N = 1010;
const int INF = 0x3f3f3f3f;
int n, m, t, k;
//int number[10], id[10];
//int cntarr, cntindex = 11;
int f[N];
string name[N];
int cnt1[N];
int findid(string nx)
{
for(int i = 1; i <= n; i++)
if(name[i] == nx) return i;
return 0;
}
int find(int x)
{
return f[x] == x ? x : f[x] = find(f[x]);
}
void merge(int fa, int fb)
{
f[fa] = fb;
return ;
}
int main()
{
js;
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> name[i];
f[i] = i;
}
cin >> t;
while(t--)
{
string na, nb;
cin >> na >> nb;
int ida = findid(na);
int idb = findid(nb);
int fa = find(ida), fb = find(idb);
if(fa != fb) merge(fa, fb); // 如果两个人不在同一个学校，把他们合并
}
for(int i = 1; i <= n; i++)
{
int sour = find(i);
cnt1[sour] += 1; // 看看每个人的祖宗结点，也就是看自己属于哪个学校集合
}
int ans = 0, cnt = 0;
for(int i = 1; i <= n; i++) // 统计连通块个数和维护连通块最大值
if(cnt1[i])
{
cnt ++;
ans = max(cnt1[i], ans);
}
cout << cnt << ' ' << ans << '\n';
return 0;
}
【T5】包装机
【考点】栈
注意篮子里空的时候，按0是取不出物品的；同样如果传送带为空，是无法往篮子里加物品的
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#define ft first
#define sd second
#define js std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long LL;
typedef pair<string, int> PII;
//int d[N], e[N], ne[N], w[N], h[N], idx;
//int dir[4][2] = {{1,0},{0,-1},{-1,0},{0,1}};
//priority_queue<int, vector<int>, greater<int>> r;
const int N = 1010;
const int INF = 0x3f3f3f3f;
int n, m, t, k;
stack<char> r;
string s[N];
int len[N];
int main()
{
//js;
cin >> n >> t >> m;
for(int i = 1; i <= n; i++) cin >> s[i];
int op;
while(cin >> op)
{
if(op == -1) return 0;
if(op == 0 && r.size()) // 篮子不空才能拿
{
cout << r.top();
r.pop();
}
if(op == 0) continue;
if(len[op] < s[op].size()) // 传送带上有东西才能往篮子里加
{
if(r.size() == m)
{
cout << r.top();
r.pop();
}
r.push(s[op][len[op]]);
len[op] ++;
}
}
return 0;
}
【T6】求解最长递增子序列问题
【考点】LIS，但是题目没有给范围，就按照二分优化DP写了；后来发现数据很水，O(n^2)都能过
这里给出二分优化DP，不好讲，有兴趣自己百度吧
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<set>
#include<map>
#include<vector>
#define ft first
#define sd second
#define js std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
//int d[N], e[N], ne[N], w[N], h[N], idx;
//int dir[4][2] = {{1,0},{0,-1},{-1,0},{0,1}};
//priority_queue<int, vector<int>, greater<int>> r;
const int N = 100010;
int n, a[N], q[N];
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
q[1] = a[1];
int cnt = 1;
for(int i = 2; i <= n; i++)
{
if(a[i] > q[cnt])q[++cnt] = a[i];
else
*lower_bound(q + 1, q + cnt + 1, a[i]) = a[i]; // 二分优化
}
printf("%d", cnt);
return 0;
}
【T7】正整数n不同分解式的个数
【考点】因数分解，分治（可以用DP优化）
（考场上没时间写了，先附上别人的代码吧，稍后学习）
1： 分治写法
#include <iostream>
using namespace std;
int solve(int n)
{
int i;
int count = 0;
if (n == 1)
return 1;
else
for (i = 2; i <= n; i++) {
if (n%i == 0)
count += solve(n / i);
}
return count;
}
int main()
{
int n;
cin >> n;
cout << solve(n) << endl;
return 0;
}
2：
#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
int a[10000], dp[10000], k = 0;
void ul(int num)
{
int i;
for (i = 1; i < sqrt(num); i++)
{
if (num%i == 0)
{
a[k++] = i;
a[k++] = num / i;
}
}
if (i*i == num)
{
a[k++] = i;
}
}
void solve(int n)
{
int i, j;
dp[0] = 1;
for (i = 1; i < k; i++)
{
dp[i] = 0;
for (j = 0; j < i; j++)
{
if (a[i] % a[j] == 0)
{
dp[i] += dp[j];
}
}
}
}
int main()
{
int n;
cin >> n;
ul(n);//求n的约数
int t;
sort(a, a + k);
solve(n);
cout << dp[k - 1] << endl;
k = 0;
return 0;
}
京公网安备 11010502036488号