619校内练习汇总（gym+cf）
2018-06-20 本文已影响0人
weiers
比赛链接
https://vjudge.net/contest/234941
E - Game of Dice
tag：暴力法，折半搜索
题目大意
有n组数，每组6个，每组选一个数相乘，问乘积模1e9+7后等于x的组合种数。（n<=14,x<1e9+7)
解题思路
n/2组暴力dfs乘积和存入map，剩余n-n/2组dfs乘积和，在map中查找与其相乘等于x的对应数字。复杂度o(6^(n/2))
F - Strings and Queries
Gym - 101532F
tag：RMQ 回文子串数
题目大意
给你n个字符串，q次查询，每次查询给两个字符串a,b，且a,b一定在之前给的字符串当中，求a，b两个字符串之间（包括其本身）回文子串数量最多的字符串下标。（n<=1e4,q<=1e5)
解题思路
- 预处理出每个字符串的回文子串数量
- RMQ查询，注意返回的是字符串下标，多开一个数组，或者开一个结构体即可。
- 注意在使用map查询字符串a,b所对应的下标时，需要把字符串hash，因为map中字符串比较花费时间较大，会t。
- 类似于dp思想求回文子串数量学习一下
int nump(string s){
int len=s.size();
int sum=0;
memset(c,0,sizeof(c));
for(int i=len-1;i>=0;i--)
{
c[i][i]=true;
sum++;
for(int j=i+1;j<len;j++)
{
if(s[i]==s[j])
{
if(i+1==j||c[i+1][j-1])
{
c[i][j]=true;
sum++;
}
}
else c[i][j]=false;
}
}
return sum;
}
- 再放下RMQ部分代码
void ST(int n) {
for (int j = 1; (1 << j) <= n; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
if(dp[i][j - 1]>= dp[i + (1 << (j - 1))][j - 1]) {
dp[i][j]=dp[i][j - 1];
in[i][j]=in[i][j-1];
}
else{
dp[i][j]=dp[i + (1 << (j - 1))][j - 1];
in[i][j]=in[i + (1 << (j - 1))][j - 1];
}
}
}
}
int RMQ(int l, int r) {
int k = 0;
while ((1 << (k + 1)) <= r - l + 1) k++;
if(dp[l][k]>=dp[r - (1 << k) + 1][k])
return in[l][k];
else return in[r - (1 << k) + 1][k];
}
L - List Of Integers
题目大意
求大于x且与p互质的第k大的数。（x,p,k<=1e6)
解题思路
- 求n以内与p互质的数，只要容斥每个质因子的倍数即可
- 二分答案n
- 预处理<=1e6的所有数的质因子（一个数的质因子个数不超过10个）
代码实现
#include<cstdio>
#include<iostream>
#include<queue>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<sstream>
#include<algorithm>
#define pb(x) push_back(x)
#define fir first
#define sec second
#define mem(a,x) memset(a,x,sizeof(a))
typedef long long ll;
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1e6+100;
vector<int>d[maxn];
int vis[maxn];
/**预处理质因子**/
void init(){
memset(vis,0,sizeof(vis));
for(int i=2;i<maxn;i++){
if(!vis[i]){
for(int j=i;j<maxn;j+=i)
{
d[j].push_back(i);
vis[j]=1;
}
}
}
}
/**容斥原理**/
ll cal(ll x,int p){
int m=d[p].size();
ll num=0;
for(int i=1;i<(1<<m);i++){
ll ans=1;int ant=0;
for(int j=0;j<m;j++){
if(i&(1<<j)){
ans*=d[p][j];
ant++;
}
}
if((ant-1)%2) num-=(x/ans);
else num+=(x/ans);
}
return x-num;
}
int main(){
int t;
init();
scanf("%d",&t)==1;
while(t--){
ll x,p,k;
scanf("%lld%lld%lld",&x,&p,&k);
ll ans1=cal(x,p);
/**二分答案**/
ll low=x+k-1;ll high=1e8;
ll ans=-1;
while(high-low>1){
int mid=(high+low)/2;
ll ans2=cal(mid,p)-ans1;
if(ans2>=k) high=mid;
else low=mid;
}
printf("%lld\n",high);
}
}
N - Sleepy Game
题目大意
有向图中从s出发，一人一步至无路可走，无路可走者输。p先走，且p每次选择最佳走法，v也每次选择有利于p的走法。若陷入循环，无法出去，则平局。问p是否能赢，还是输还是平局。赢则打印路径。（n个点，m条路 2 ≤ n ≤ 105, 0 ≤ m ≤ 2*1e5）
解题思路
- 即求是否有一条从s出发，经过奇数条边后出度为0的路径。
- 拆点dfs，每个点在路径上是第奇数个/偶数个点分别访问标记。
- 判断是否平局，看是否有从s出发的环。dfs染色，访问过则标记1，访问过且出栈标记2。
- 判环不能用拓扑排序，因为不能保证该环是从s出发能到达的。
代码实现
#include<cstdio>
#include<iostream>
#include<queue>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<sstream>
#include<algorithm>
#define pb(x) push_back(x)
#define fir first
#define sec second
#define mem(a,x) memset(a,x,sizeof(a))
typedef long long ll;
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1e5+100;
int h[maxn];
int vis[maxn][2];
int p[maxn][2];
vector<int>edge[maxn];
void dfs(int x,int st,int pre){
p[x][st]=pre;
vis[x][st]=1;
int flag=0;
for(int i=0;i<edge[x].size();i++){
int t=edge[x][i];
if(!vis[t][st^1]) dfs(t,st^1,x);
}
}
/**判环**/
bool huan(int x){
h[x]=1;
for(int i=0;i<edge[x].size();i++){
int t=edge[x][i];
if(h[t]==1||h[t]==0&&huan(t)) return 1;
}
h[x]=2;
return 0;
}
/**打印路径**/
void print(int x,int st){
if(x==0) return;
print(p[x][st],st^1);
printf("%d ",x);
}
int main(){
int n,m;
while(scanf("%d%d",&n,&m)==2){
memset(vis,0,sizeof(vis));
memset(h,0,sizeof(h));
for(int i=0;i<=n;i++)
edge[i].clear();
int c;
for(int i=1;i<=n;i++){
scanf("%d",&c)==1;
for(int j=1;j<=c;j++)
{
int t;
scanf("%d",&t);
edge[i].push_back(t);
}
}
int s;
scanf("%d",&s);
dfs(s,1,0);
int flag=0;
for(int i=1;i<=n;i++){
if(vis[i][0]&&edge[i].size()==0)
{
flag=1; printf("Win\n"); print(p[i][0],1);
printf("%d\n",i);
break;
}
}
if(flag==0){
if(huan(s)) printf("Draw\n");
else printf("Lose\n");
}
}
return 0;
}
