题目链接：http://codeforces.com/contest/762
A. k-th divisor
题意：很简单 求n的第k大的因子如果不存在k个因子 输出-1，注意到n的范围 直接for 1-n 做会超时
解法：我直接把所有的因子存到vector排序，竟然水过了。。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
vector <LL> v;
int main(){
LL n, k;
cin >> n >> k;
for(LL i=1; i*i<=n; i++){
if(n%i==0){
v.push_back(i);
if(n/i!=i){
v.push_back(n/i);
}
}
}
sort(v.begin(),v.end());
if(k>v.size()) puts("-1");
else printf("%lld\n", v[k-1]);
return 0;
}B. USB vs. PS/2
题意：有n台电脑其中有的电脑只能接usb，有的电脑只能接ps/2有的电脑两者都兼容，然后买了m个鼠标，问你能否使他们都配上电脑
解法：对于不能兼容的电脑先贪心地选取合适线的鼠标，最后再选兼容的电脑
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
priority_queue <LL,vector<LL>,greater<LL> > q1,q2;
int main(){
int a, b, c, m;
scanf("%d %d %d", &a,&b,&c);
scanf("%d", &m);
for(int i=1; i<=m; i++){
string s;
LL x;
cin >> x >> s;
if(s=="USB") q1.push(x);
else q2.push(x);
}
int ans1 = 0;
LL ans2 = 0;
while(!q1.empty()&&a>0){
--a;
ans1++;
ans2+=q1.top();
q1.pop();
}
while(!q2.empty()&&b>0){
--b;
ans1++;
ans2+=q2.top();
q2.pop();
}
while(c>0){
if(q1.empty()&&q2.empty()) break;
else if(q1.empty()){
--c;
ans1++;
ans2+=q2.top();
q2.pop();
}else if(q2.empty()){
--c;
ans1++;
ans2+=q1.top();
q1.pop();
}
else{
--c;
if(q1.top()<q2.top()){
ans1++;
ans2+=q1.top();
q1.pop();
}else{
ans1++;
ans2+=q2.top();
q2.pop();
}
}
}
return 0*printf("%d %lld\n", ans1, ans2);
}C. Two strings
题意：给定两个字符串a,b，让你去b中的一个连续的字段，使剩余的b串中的拼接起来的两个串是a穿的子序列。最大化这个字串的长度。
解法：开始完全不会做这个问题，然后参考了这个题解：https://www.cnblogs.com/Skyminer/p/6352067.html
删除这个操作不太好说，我们先换一个思路:实际上删除就是在b串中分别取出两个不相交的前缀和后缀，使得这两个串在a串中不重叠地出现
我们发现答案具有显然的单调性，所以我们首先二分答案(二分删去的字串长度)。
现在来考虑如何进行判定:
一个很直接的思路就是枚举所有的符合条件的前缀和后缀
然后对这个前缀求其在a中的最靠左的子序列的右端下标。
相应的后缀也这么处理.
如: a = "abbcbc",pre = "abc" [数组下标从1开始]
那么串pre,在a中最靠左的子序列有段下标为4.
那么我们我们只要找到一个点，从这个点劈开后，前缀的下标 < 后继的下标即可
枚举O(n)求出在a序列中拓展到的位置(O(n),总时间复杂度为O(n^2logn)
TLE
我们发现每次对一个前缀求在a中出现的下标都是重复的问题
所以我们O(n)预处理一遍(后缀是类似的)
所以我们就做到了O(n)判定
时间复杂度O(nlogn)
妙啊。。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200010;
char a[maxn], b[maxn];
int pre[maxn], suf[maxn];
int main(){
scanf("%s %s", a+1,b+1);
int n = strlen(a+1);
int m = strlen(b+1);
for(int i=1,j=0;b[i];i++){
++j;
while(b[i]!=a[j]&&j<=n) ++j;
pre[i]=j;
}
for(int i=m,j=n+1;b[i];i--){
--j;
while(b[i]!=a[j]&&j>0) --j;
suf[i]=j;
}
suf[m+1] = n+1;
int i;
int ans1,ans2,l=0,r=m;
while(l<=r){
int mid=(l+r)/2;
for(i=0; i+mid<=m; i++) if(pre[i]<suf[i+mid+1]) break;
if(i+mid<=m){
ans1=i,ans2=i+mid+1,r=mid-1;
}else l=mid+1;
}
if(ans2-ans1>m) return 0*puts("-");
else{
for(i=1; i<=ans1; i++) printf("%c", b[i]);
for(i=ans2;b[i];i++) printf("%c", b[i]);
printf("\n");
}
}D. Maximum path
题意：给一个3*n的网格图，找一条从左上到右下的路径使得点权和最大
解法：
我做的时候完全想不到这种做法啊，感觉插头可以做，可是不会插头，无脑选手要去恶补一下插头了啊。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL inf = 1e16;
const int maxn = 100010;
int n, a[3][maxn];
LL dp[maxn][4];
LL sum(int x, int l, int r){
if(l > r) swap(l, r);
LL ret = 0;
for(int i=l; i<=r; i++) ret += a[i][x];
return ret;
}
int main(){
scanf("%d", &n);
for(int i=0; i<3; i++)
for(int j=1; j<=n; j++)
scanf("%d", &a[i][j]);
for(int i=0; i<=n; i++)
for(int j=0; j<4; j++)
dp[i][j] = -inf;
dp[0][0]=0;
for(int i=1; i<=n; i++){
for(int j=0; j<3; j++)
for(int k=0; k<3; k++)
dp[i][j] = max(dp[i][j], dp[i-1][k]+sum(i, j, k));
dp[i][0] = max(dp[i][0], dp[i-1][3]+sum(i,0,2));
dp[i][2] = max(dp[i][2], dp[i-1][3]+sum(i,0,2));
dp[i][3] = max(dp[i][3], max(dp[i-1][0], dp[i-1][2])+sum(i,0,2));
}
return 0*printf("%lld\n", dp[n][2]);
}题意：题目中给的那几个式子，求满足要求的对数
解法：先对点进行排序，排序为对半径降序。然后由于k很小，所以可以枚举所有相近的频率，并在对应的线段树中进行坐标区间查找。枚举完毕后，将这个点加入对应频率的线段树中。由于半径由大到小枚举，所以后面的如果包含前面的，那么前面的也必然包含后面的。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 100010;
const int maxm = 40*maxn;
LL n, k, rt[maxn], ls[maxm], rs[maxm], cnt[maxm], tot;
void update(LL l, LL r, LL &now, LL pos){
if(!now) now = ++tot;
if(l == r){
cnt[now]++;
return;
}
int mid = (l+r)/2;
if(pos <= mid) update(l, mid, ls[now], pos);
else update(mid+1, r, rs[now], pos);
cnt[now] = cnt[ls[now]] + cnt[rs[now]];
}
LL query(LL l, LL r, LL now, LL L, LL R){
if(!now) return 0;
if(L<=l&&r<=R) return cnt[now];
int mid = (l+r)/2;
if(R<=mid) return query(l, mid, ls[now], L, R);
else if(L>mid) return query(mid+1, r, rs[now], L, R);
else return query(l, mid, ls[now], L, R) + query(mid+1, r, rs[now], L, R);
}
struct node{
LL x, r, f;
node(){}
node(LL _x, LL _r, LL _f){
x = _x;
r = _r;
f = _f;
}
bool operator<(const node &rhs) const{
return r > rhs.r;
}
void read(){
scanf("%lld %lld %lld", &x, &r, &f);
}
}a[maxn];
int pos[maxn];
int main(){
scanf("%lld %lld", &n,&k);
for(int i=1; i<=n; i++) a[i].read(), pos[i] = i;
sort(a+1, a+n+1);
LL ans = 0;
for(LL i=1; i<=n; i++){
LL id = pos[i];
for(LL j=max(a[id].f-k, 1LL); j<=min(a[id].f+k, 10000LL); j++)
ans += query(1, 1000000000LL, rt[j], max(a[id].x-a[id].r, 1LL), min(a[id].x+a[id].r, 1000000000LL));
update(1, 1000000000LL, rt[a[id].f], a[id].x);
}
return 0*printf("%lld\n", ans);
}F. Tree nesting
感觉神题啊。
参考题解：http://blog.csdn.net/wxh010910/article/details/54784089
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
const int maxv = 1<<12;
const int mod = 1e9+7;
int qsm(int a, int n){
int ret = 1;
while(n){
if(n&1) ret=1LL*ret*a%mod;
a = 1LL*a*a%mod;
n>>=1;
}
return ret;
}
struct edge{int to,next;};
struct tree{
edge e[maxn<<1];
int n,edgecnt;
int head[maxn],son[maxn][maxn],sz[maxn],bit[maxn];
void init(){memset(head,0,sizeof(head));edgecnt=0;}
void add(int x,int y){e[++edgecnt].to=y,e[edgecnt].next=head[x],head[x]=edgecnt;}
void read(){
init();
scanf("%d",&n);
for(int i=1; i<n; i++){
int x, y;
scanf("%d %d", &x,&y);
add(x,y);
add(y,x);
}
}
void dfs(int x, int fa){
sz[x]=bit[x]=0;
for(int i=head[x];i;i=e[i].next){
int v = e[i].to;
if(v == fa) continue;
dfs(son[x][++sz[x]]=e[i].to,x), bit[x]|=1<<e[i].to-1;
}
}
}S,T;
int dp[maxn][maxv], ans, ans2;
//dp[i][j]表示S中i的子树和右兄弟（不包括i）完成T的状态为j的方案数
bool vis[maxn][maxv];
//dfs(f,y,V)表示f的第y个儿子，状态为V方便转移
int dfs(int f, int y, int V){
if(!y) return !V;
int x = S.son[f][y];
if(vis[x][V]) return dp[x][V];
vis[x][V] = 1;
int &ret = dp[x][V];
ret = dfs(f, y-1, V);
for(int i=0; i<T.n; i++) if(V>>i&1)
ret = (1LL*dfs(f, y-1, V^(1<<i))*dfs(x, S.sz[x],T.bit[i+1]) + ret)%mod;
return ret;
}
int main(){
S.read();T.read();S.dfs(1,0);
for(int i=1; i<=T.n; i++){
memset(dp, 0, sizeof(dp));
memset(vis, 0, sizeof(vis));
T.dfs(i, 0);
for(int j=1; j<=S.n; j++)(ans += dfs(j,S.sz[j],T.bit[i]))%=mod;
}
S = T; S.dfs(1, 0);
for(int i=1; i<=T.n; i++){
memset(dp, 0, sizeof(dp));
memset(vis, 0, sizeof(vis));
T.dfs(i,0);
(ans2+=dfs(1,S.sz[1],T.bit[i]))%=mod;
}
ans=(1LL*ans%mod*qsm(ans2,mod-2)%mod)%mod;
return 0*printf("%d\n", ans);
}
京公网安备 11010502036488号