爆炸的一场,脑子已经放弃我了。。
A -思维 题意:数组a、b,可对数组重排,令c[i]=a[i]+b[i],求c中第k大的数的最大值。 思路:a中的前k大和b中的前k大倒序组合,取最小值 B-图论 题意: 1e6个点的有向图,每个点只有一条指出的边,问图中最长的简单路径包含的点数 思路:图中一定会出现环。对于环,从环内所有点出发的最长简单路径的点数=该环内包含的点数,可以先把能够直接统计的答案处理出来。注意每个点只能访问一次,避免复杂度退化,再以每个点为起点记忆化dfs求答案。 ac代码:#include
using namespace std;
const int maxn = 1e6+10;
int to[maxn], ans[maxn];
bool vis[maxn], ins[maxn];//ins标记是否在当前处理的栈中
stack s;
int n;
int dfs(int x)
{
if(ans[x]) return ans[x];
else return ans[x] = dfs(to[x])+1;
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &to[i]);
for(int i = 1; i ..->j
{
int cnt = 1, oj = j;
while(to[j]!=oj) cnt++, j = to[j];
ans[oj] = cnt; j = oj;
while(to[j]!=oj) j = to[j], ans[j] = cnt;//直接统计环内答案
}
while(!s.empty()) ins[s.top()] = false, s.pop();
}
}
int res = 0;
for(int i = 1; i <= n; i++)//从每个点出发的最长简单路径,记忆化
res = max(res, dfs(i));
cout << res;
return 0;
}
C - Dilworth+最长下降子序列nlogn求法
题目:给定1e5个(x,y),保证x互不相等且y互不相等。求最少可以将这些(x,y)划分成多少组,每组内按照x,y升序排列后都满足ai<ai+1a_i<a_{i+1}ai<ai+1 且bi<bi+1b_i<b_{i+1}bi<bi+1,并输出组数和原始(x,y)所在分组的编号
思路:先将x升序排列,那么只需要考虑最少把y划分成多少组,每组内的y是严格升序的。根据Dilworth定理,可以转化为最长严格下降子序列的长度(bi>bi+1b_i>b_{i+1}bi>bi+1),最后的组数就等于此长度。在用二分法求最长下降子序列长度时,将求解过程中存储在同一下标的元组分到一组。I | Y[] |
---|---|
1 | {1} |
2 | {2} |
3 | {5} |
4 | {5, 4} |
5 | {5, 4, 3} |
6 | {9, 4, 3} |
7 | {9, 7, 3} |
8 | {9, 7, 6} |
所以最终分组为{1, 2, 5, 9} 、{4, 7}、{3, 6} 组数为3
ac代码:
#include
using namespace std;
const int maxn = 1e5+10;
struct node{
int x, y, oid;
friend bool operator < (node a, node b)
{
return a.x < b.x;
}
}a[maxn];
int Y[maxn], ans[maxn];
int n;
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d %d", &a[i].x, &a[i].y), a[i].oid = i;
sort(a+1, a+1+n);
int len = 0;
Y[0] = INT_MAX;
for(int i = 1; i <= n; i++)
{
//cout << a[i].y << " " << Y[len] << endl;
if(a[i].y<Y[len]) Y[++len] = a[i].y, ans[a[i].oid] = len;
else
{
int it = lower_bound(Y+1, Y+1+len, a[i].y, greater()) - Y;//第一个小于x的下标
Y[it] = a[i].y;
ans[a[i].oid] = it;
}
}
printf("%d\n", len);
for(int i = 1; i <= n; i++)
printf("%d%c", ans[i], i==n?'\n':' ');
return 0;
}
D-计数
题意:给定两个序列A,B,问A有多少种排列方式使得Ai<=BiA_i<=B_iAi<=Bi,相同的数字视为不同,如11有两种排列方式
思路:将A,B排序,考虑B的每一位当前可填的数字有多少个。(也可从大到小考虑A中的每一个数字,在B中有多少位置可填,下一次的可填位置数受上一次影响)
E-贪心
题意:1e5组样例,每次询问最大的正整数A,存在正整数B,满足A3B=NA^3B=NA3B=N。1≤N≤1e181≤N≤1e181≤N≤1e18
思路:先筛出一定范围内的质数(39000和49000都可过,太小不行),用这些质数去除N(质数3^33|N的话此时可以统计答案了),那么剩下的数如果是立方数的话对答案有贡献,更新答案,否则就无贡献。二分判断一个数是否是立方数。
ac代码:
#include
using namespace std;
typedef long long ll;
const int maxn = 1e6+10;
int v[maxn], prime[maxn];
ll sc[maxn];
int m = 0;
inline ll read()
{
ll s = 0, f = 1;
char ch = getchar();
for(; ch '9'; ch = getchar()) if(ch == '-') f = - 1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 3ll) + (s << 1ll) + (ch ^ 48ll));
return s * f ;
}
void pre()//5035个质数
{
for(int i = 2; i <= 49000; i++)
{
if(v[i] == 0)
{
v[i] = i;
prime[++m] = i;
sc[m] = 1ll*i*i*i;
}
for(int j = 1; j v[i] || prime[j]*i>1e6) break;
v[i*prime[j]] = prime[j];
}
}
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
pre();
int t; ll n;
scanf("%d", &t);
while(t--)
{
//scanf("%lld", &n);
n = read();
ll ans = 1;
for(int i = 1; i =prime[i]; i++)
{
if(n%prime[i]==0)
{
while(n%sc[i]==0)
{
ans *= prime[i];
n /= sc[i];
}
while(n%prime[i]==0) n/=prime[i];
}
}
ll l = 1, r = 1e6;
while(l>1;
if(mid*mid*mid<n) l = mid+1;
else r = mid-1;
}
if(l*l*l==n) ans *= l;
printf("%lld\n", ans);
}
return 0;
}
F 签到
G 签到
H - 思维
题意:矩形边平行于坐标轴,且会退化为点或线段。A类矩形在第三象限且向右移动,B类矩形在第一象限,且向下移动。问有的多少对A类矩形和B类矩形会相交。
思路:转化为相对运动考虑。假设第一象限的矩形不动,那么第三象限的矩形在向右上方移动,且会穿过y=-x,将A,B矩形投影在y=-x上,若线段有交点则原AB矩形会相交。#include
using namespace std;
typedef long long ll;
const int maxn = 4e5+10;
struct node{
int x, lr, type;//lr=1 投影右端
friend bool operator b.lr;
return a.x < b.x;
}
}a[maxn];
ll cnt[3];
inline int read()
{
int s = 0, f = 1;
char ch = getchar();
for(; ch '9'; ch = getchar()) if(ch == '-') f = - 1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 3ll) + (s << 1ll) + (ch ^ 48ll));
return s * f ;
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
int n, m, x, y, p, q;
scanf("%d %d", &n, &m);
int num = 0;
for(int i = 1; i <= n; i++)
{
x = read(), y = read(), p = read(), q = read();
a[++num] = node{y-x, -1, 0};
a[++num] = node{q-p, 1, 0};
}
for(int i = 1; i <= m; i++)
{
x = read(), y = read(), p = read(), q = read();
a[++num] = node{y-x, -1, 1};
a[++num] = node{q-p, 1, 1};
}
sort(a+1, a+1+num);
ll ans = 0;
for(int i = 1; i <= num; i++)
{
cnt[a[i].type] += a[i].lr;
if(a[i].lr==1) ans += cnt[a[i].type^1];
}
cout << ans;
return 0;
}
I - 思维+kruskal
题意:原图N个点,N-1条边链接。现给出矩阵a, a[i][j]表示i->j的最短距离。判读是否存在一个原图满足矩阵a。满足升序输出N-1条道路的长度。
思路:(1)题目没有保证输入的矩阵对称,为了保险起见,判断一下。#include
using namespace std;
const int maxn = 510;
struct node{
int x, y, val;
friend bool operator < (node a, node b)
{
return a.val < b.val;
}
}edge[maxn*(maxn-1)/2+10];
struct NODE{
int id, val;
};
vector link[maxn];//与当前节点相连的所有点及其距离
int fa[maxn], ans[maxn], a[maxn][maxn], dis[maxn][maxn];
int n;
int find_fa(int x)
{
return fa[x]==x ? x : fa[x]=find_fa(fa[x]);
}
void dfs(int st, int now, int pre, int d)
{
dis[st][now] = d;
for(int i = 0; i < link[now].size(); i++)
{
int nxt = link[now][i].id, val = link[now][i].val;
if(nxt!=pre) dfs(st, nxt, now, d+val);
}
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
scanf("%d", &n);
for(int i = 1; i <= n; i++) fa[i] = i;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
scanf("%d", &a[i][j]);
int num = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(a[i][j]!=a[j][i])//题目没有保证输入的矩阵绝对是对称的
{
printf("No\n");
return 0;
}
if(i<j) edge[++num] = node{i, j, a[i][j]};
}
}
sort(edge+1, edge+1+num);
for(int i = 1, cnt = 0; i <= num; i++)
{
int x = find_fa(edge[i].x), y = find_fa(edge[i].y);
if(x!=y)
{
fa[x] = y;
int xx = edge[i].x, yy = edge[i].y, val = edge[i].val;
ans[++cnt] = val;
link[xx].push_back(NODE{yy, val});
link[yy].push_back(NODE{xx, val});
}
}
for(int i = 1; i <= n; i++) dfs(i, i, 0, 0);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(a[i][j]!=dis[i][j])
{
printf("No\n");
return 0;
}
printf("Yes\n");
for(int i = 1; i < n; i++) printf("%d\n", ans[i]);
return 0;
}
J 签到