比賽鏈接
https://vjudge.net/contest/234941
E - Game of Dice
tag：暴力法，折半搜索
題目大意
有n組數(shù)，每組6個(gè)，每組選一個(gè)數(shù)相乘，問(wèn)乘積模1e9+7后等于x的組合種數(shù)。（n<=14,x<1e9+7)
解題思路
n/2組暴力dfs乘積和存入map，剩余n-n/2組dfs乘積和，在map中查找與其相乘等于x的對(duì)應(yīng)數(shù)字。復(fù)雜度o(6^(n/2))
F - Strings and Queries
Gym - 101532F
tag：RMQ 回文子串?dāng)?shù)
題目大意
給你n個(gè)字符串，q次查詢，每次查詢給兩個(gè)字符串a(chǎn),b，且a,b一定在之前給的字符串當(dāng)中，求a，b兩個(gè)字符串之間（包括其本身）回文子串?dāng)?shù)量最多的字符串下標(biāo)。（n<=1e4,q<=1e5)
解題思路
- 預(yù)處理出每個(gè)字符串的回文子串?dāng)?shù)量
- RMQ查詢，注意返回的是字符串下標(biāo)，多開(kāi)一個(gè)數(shù)組，或者開(kāi)一個(gè)結(jié)構(gòu)體即可。
- 注意在使用map查詢字符串a(chǎn),b所對(duì)應(yīng)的下標(biāo)時(shí)，需要把字符串hash，因?yàn)閙ap中字符串比較花費(fèi)時(shí)間較大，會(huì)t。
- 類似于dp思想求回文子串?dāng)?shù)量學(xué)習(xí)一下
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互質(zhì)的第k大的數(shù)。（x,p,k<=1e6)
解題思路
- 求n以內(nèi)與p互質(zhì)的數(shù)，只要容斥每個(gè)質(zhì)因子的倍數(shù)即可
- 二分答案n
- 預(yù)處理<=1e6的所有數(shù)的質(zhì)因子（一個(gè)數(shù)的質(zhì)因子個(gè)數(shù)不超過(guò)10個(gè)）
代碼實(shí)現(xiàn)
#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];
/**預(yù)處理質(zhì)因子**/
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出發(fā)，一人一步至無(wú)路可走，無(wú)路可走者輸。p先走，且p每次選擇最佳走法，v也每次選擇有利于p的走法。若陷入循環(huán)，無(wú)法出去，則平局。問(wèn)p是否能贏，還是輸還是平局。贏則打印路徑。（n個(gè)點(diǎn)，m條路 2?≤?n?≤?105, 0?≤?m?≤?2*1e5）
解題思路
- 即求是否有一條從s出發(fā)，經(jīng)過(guò)奇數(shù)條邊后出度為0的路徑。
- 拆點(diǎn)dfs，每個(gè)點(diǎn)在路徑上是第奇數(shù)個(gè)/偶數(shù)個(gè)點(diǎn)分別訪問(wèn)標(biāo)記。
- 判斷是否平局，看是否有從s出發(fā)的環(huán)。dfs染色，訪問(wèn)過(guò)則標(biāo)記1，訪問(wèn)過(guò)且出棧標(biāo)記2。
- 判環(huán)不能用拓?fù)渑判颍驗(yàn)椴荒鼙ＷC該環(huán)是從s出發(fā)能到達(dá)的。
代碼實(shí)現(xiàn)
#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);
}
}
/**判環(huán)**/
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;
}
