传送门

D - Decimal

题意：

询问\(\frac{1}{n}\)是否为有限小数。

思路：

拆质因子，看是不是只包含2和5即可，否则除不尽。

Code 
#include <bits/stdc++.h>

#define MP make_pair

#define fi first

#define se second

#define sz(x) (int)(x).size()

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

const int N = 1e5 + 5;

int t,n;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(0); cout.tie(0);

#ifdef Local

    freopen("../input.in", "r", stdin);

    freopen("../output.out", "w", stdout);

#endif

    cin>>t;

    while(t--){

        cin>>n;

        while(n%2==0){

            n/=2;

        }

        while(n%5==0){

            n/=5;

        }

        if(n!=1)cout<<"Yes\n";

        else cout<<"No\n";

    }

    return 0;

}

E - Escape

因为网上很多代码都有点问题，所以单独写了一下：传送门

F - Forest Program

题意：

给出一个仙人掌图（每条边最多在一个简单环中），可能不联通。

问有多少种删边方法能使得这个图变为森林。

思路：

显然对于环上的边我们至少删一条边，其它边随便删，所以关键就是找简单环。

一开始纠结点双什么的，魔改tarjan...

后面发现直接dfs找环就行，环长可以直接利用深度来求。

Code 
#include <bits/stdc++.h>

#define MP make_pair

#define fi first

#define se second

#define sz(x) (int)(x).size()

//#define Local

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

const int N = 1e5 + 5;

const int MAXN=3e5+5,MAXM=1e6+5,MOD=998244353;

struct Edge{

    int v,next;

}e[MAXM];

int n,m,u,v,head[MAXN],cnt,dep[MAXN];

ll ans=1,pw[500005];

bool vis[MAXN],ins[MAXN];

inline void addEdge(int u,int v){

    e[++cnt] = {v,head[u]};head[u] = cnt;

}

void dfs(int u,int f){

    ins[u]=vis[u]=1;

    dep[u] = dep[f] + 1;

    for(int i=head[u];i;i=e[i].next){

        int v=e[i].v;

        if(v==f)continue;

        if(ins[v]){

            ans = ans * (pw[dep[u]-dep[v]+1]-1+MOD)%MOD;

            m-=dep[u]-dep[v]+1;

        }

        if(vis[v])continue;

        dfs(v,u);

    }

    ins[u]=0;

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(0); cout.tie(0);

    //cout << fixed << setprecision(20);

#ifdef Local

    freopen("../input.in", "r", stdin);

    freopen("../output.out", "w", stdout);

#endif

    pw[0]=1;

    for(int i=1;i<=500000;i++)pw[i]=pw[i-1]*2%MOD;

    cin>>n>>m;

    for(int i=1;i<=m;i++){

       cin>>u>>v;

       addEdge(u,v);addEdge(v,u);

    }

    for(int i=1;i<=n;i++){

        if(!vis[i])dfs(i,0);

    }

    cout<<ans*pw[m]%MOD<<'\n';

    return 0;

}

### I - Invoker
似乎是直接暴力dp+模拟。

Code 
#include <bits/stdc++.h>

using namespace std;

#define REP(i,a,b) for(register int i=(a);i<(b);i++)

inline int calc();

#define MAXN 3*3*3+7

int dis[MAXN][MAXN];

bool vis[MAXN];

vector<int> pers[17];

inline int skilltoid(int a, int b, int c) {

        int k=(1<<(2*a))+(1<<(2*b))+(1<<(2*c));

        #define F(x,y,z) ((1<<(2*x))+(1<<(2*y))+(1<<(2*z)))

        #define Q 0

        #define W 1

        #define E 2

        switch(k) {

            case F(Q, Q, Q): return 1;

            case F(Q, Q, W): return 2;

            case F(Q, Q, E): return 3;

            case F(W, W, W): return 4;

            case F(Q, W, W): return 5;

            case F(W, W, E): return 6;

            case F(E, E, E): return 7;

            case F(Q, E, E): return 8;

            case F(W, E, E): return 9;

            case F(Q, W, E): return 10;

        }

        return -1;

        #undef F

        #undef Q

        #undef W

        #undef E

}

inline int id(int a,int b,int c) {

    return 3*3*a+3*b+c+1;

}

inline void test(int z) {

    const char x[]="QWE";

    REP(a,0,3)REP(b,0,3)REP(c,0,3) if(z==id(a,b,c)) {printf("%c%c%c",x[a],x[b],x[c]);}

}

inline int chtoid(char x) {

    switch(x) {

        case 'Y': return 1;

        case 'V': return 2;

        case 'G': return 3;

        case 'C': return 4;

        case 'X': return 5;

        case 'Z': return 6;

        case 'T': return 7;

        case 'F': return 8;

        case 'D': return 9;

        case 'B': return 10;

    }

    return 0;

}

inline void genpers() {

        pers[0].push_back(0);

    REP(a,0,3)REP(b,0,3)REP(c,0,3) {

        int sid=skilltoid(a,b,c);

        pers[sid].push_back(id(a,b,c));

    }

}

struct node{

    int a,b,c;

    int l;

};

queue<node> q;

inline void gendis(int a,int b,int c) {

    memset(vis,0,sizeof vis);

    int nid;

    int mid=id(a,b,c); dis[0][mid]=3; vis[mid]=1;

    q.push((node){a,b,c,0});

    dis[mid][mid]=0;

    while(!q.empty()) {

        node now=q.front(); q.pop();

        REP(d,0,3) {

            nid=id(now.b,now.c,d);

            if(!vis[nid]) {

                q.push((node){now.b,now.c,d,now.l+1});

                vis[nid]=1;

                dis[mid][nid]=now.l+1;

            }

        }

    }

}

char seq[100007];

int dp[2][9];

int main() {

    genpers();

    REP(a,0,3)REP(b,0,3)REP(c,0,3){gendis(a,b,c);}

    scanf("%s", seq);

    int len=strlen(seq);

    int t=0, lst=0, now=0;

    REP(i,0,9) dp[t][i]=0;

    REP(i,0,len) {

        lst=now; t^=1; char ch=seq[i]; now=chtoid(ch);

        REP(k,0,pers[now].size()) {

            dp[t][k]=0x3f3f3f3f;

            int p;

            REP(j,0,pers[lst].size()) {

                //if(dp[t^1][j]+dis[pers[lst][j]][pers[now][k]]<=dp[t][k])

                  //  test(pers[lst][j]), putchar('>'),

                    //test(pers[now][k]), printf("%d\n", dis[pers[lst][j]][pers[now][k]]);

                dp[t][k]=min(dp[t][k],dp[t^1][j]+dis[pers[lst][j]][pers[now][k]]);

            }

        }

        //putchar('\n');

    }

    int ans=0x7fffffff;

    REP(i,0,pers[now].size()) {

        ans=min(ans,dp[t][i]);

    }

    printf("%d\n", ans+len);

    return 0;

}

J - MUV LUV EXTRA

题意：

给出一串数字，定义\(l\)为某个循环节的长度，\(p\)为循环节出现的总长度（直到某尾才行）。

一个循环节对答案的贡献为\(a\cdot p-b\cdot l\)，问最大贡献是多少。

思路：

如果我们贪心来思考的话，\(p\)肯定越大越好，\(l\)肯定越小越好。所以基本思路就是找到一个最小循环节。

因为每次循环节要直至末尾，所以我们要找\(i\cdots n,1\leq i\leq n\)的所有最小循环节。

删除一个数的贡献不容易，就考虑添加，那么倒过来直接KMP即可。

Code 
#include <bits/stdc++.h>

#define MP make_pair

#define fi first

#define se second

#define sz(x) (int)(x).size()

#define all(x) (x).begin(), (x).end()

// #define Local

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

const int N = 1e7 + 5;

ll a, b;

char s[N], t[N];

int nxt[N];

void Get_next(char *s) {

	int j, L = strlen(s + 1);

	nxt[1] = j = 0;

	for(int i = 2; i <= L; i++) {

		while(j && s[i] != s[j + 1]) j = nxt[j];

		if(s[i] == s[j + 1]) ++j;

		nxt[i] = j;

	}

}

void run() {

	cin >> (s + 1);

	int n = strlen(s + 1), m = 0;

	bool ok = 0;

	for(int i = 1; i <= n; i++) {

		if(s[i] == '.') {

			ok = 1;

		} else {

			if(ok == 0) continue;

			t[++m] = s[i];

		}

 	}

 	n = m;

	reverse(t + 1, t + n + 1);

	Get_next(t);

	ll ans = -2666666666666666666;

	for(int i = 1; i <= n; i++) {

		int l = i - nxt[i], p = i;

		ans = max(ans, a * p - b * l);

	}

	cout << ans << '\n';

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(0); cout.tie(0);

    cout << fixed << setprecision(20);

#ifdef Local

    freopen("../input.in", "r", stdin);

    freopen("../output.out", "w", stdout);

#endif

    while(cin >> a >> b) run();

    return 0;

}

K - MUV LUV UNLIMITED

题意：

给出一颗以\(1\)为根的有根树，现在\(A,B\)在这颗树上玩博弈。

规则如下：每次一个人可以选择至少一个叶子结点进行删除，最后不能删除的人失败。

思路：

感觉挺有意思的一个题，定义“树枝边”为：从叶子结点往上，直到第一个分叉点的路径长度。

然后就有一个结论：

  • 若存在一个长度为\(1\)的树枝边，那么此时先手必胜。
口胡证明

若目前为一条链的情况，显然多出一条树枝边结论成立；

假设现在为多条链的情况，假设原状态为必胜态，那么多出一条边不影响；若为必败态，可以直接去掉这条树枝边把必败状态留给对方。

若多处若干树枝边，不影响结论。

所以当所有树枝边长度为\(2\)时，就时必败状态了。

现在我们已经知道树枝边小规模时的状态，那么接下来可以转换为一个石子博弈问题：给出多堆石子，每次可以选择任意堆，从上面取走一个石子，至少取一个石子，若一个人面临着存在石子数量为\(1\)的局面，就直接胜利。

这个博弈我们可以直接根据奇偶性来考虑，全为偶数时，后手有很大优势；否则，先手能将必输状态扔给对方。

代码如下：

Code 
#include <bits/stdc++.h>

#define MP make_pair

#define fi first

#define se second

#define sz(x) (int)(x).size()

#define all(x) (x).begin(), (x).end()

// #define Local

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

const int N = 1e6 + 5;

int n;

int d[N], a[N];

std::vector<int> g[N];

void dfs(int u, int fa, int &sz) {

	if(d[u] > 1) return;

	++sz;

	for(auto v : g[u]) {

		dfs(v, u, sz);

	}

}

void run() {

	cin >> n;

	for(int i = 1; i <= n; i++) d[i] = 0, g[i].clear();

	for(int i = 1; i < n; i++) {

		int x; cin >> x;

		++d[x];

		g[i + 1].push_back(x);

	}

	int tot = 0;

	for(int i = 1; i <= n; i++) {

		if(d[i] == 0) {

			int x = 0;

			dfs(i, 0, x);

			a[++tot] = x;

		}

	}

 	for(int i = 1; i <= tot; i++) {

		if(a[i] & 1) {

			cout << "Takeru" << '\n';

			return;

		}

	}

	cout << "Meiya" << '\n';

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(0); cout.tie(0);

    cout << fixed << setprecision(20);

#ifdef Local

    freopen("../input.in", "r", stdin);

    freopen("../output.out", "w", stdout);

#endif

    int T; cin >> T;

    while(T--) run();

    return 0;

}

最新文章

  1. MonoDevelop 4.2.2/Mono 3.4.0 in CentOS 6.5 安装笔记
  2. 用C表达面向对象语言的机制——C#版
  3. Centos:Another app is currently holding the yum lock; waiting for it to exit...
  4. css 图片垂直居中总结
  5. lucene.net helper类 【结合盘古分词进行搜索的小例子（分页功能）】
  6. 259. 3Sum Smaller
  7. 省市联动Demo
  8. 一种基于Qt的可伸缩的全异步C/S架构server实现(二) 网络传输
  9. C#操作Xml：XSLT语法 在.net中使用XSLT转换xml文档示例
  10. Idea中执行TestNg报错
  11. sql将一列数据拼成一个字符串的方法
  12. 师兄写的一个JAVA播放器的源代码（转）
  13. 基于SSM实现的简易员工管理系统（网站上线篇）
  14. 最新App Store审核10大被拒理由
  15. DOM是什么？有什么用处？js与DOM啥关系？
  16. InfluxDB基本概念和操作
  17. BZOJ2006[NOI2010]超级钢琴——堆+主席树
  18. 使用navicat premium将数据库从Oracle迁移到SQL Server，或从Oracle迁移到MySQL
  19. HDU1166-敌兵布阵 （线段树）
  20. ballerina 学习二十七 项目k8s部署&amp;&amp; 运行

热门文章

  1. GitHub如何配置SSH Key
  2. Appium滑动函数：Swipe()
  3. pwn-Stack Overflow
  4. SpringBoot定时器任务
  5. zz高精地图和定位在自动驾驶的应用
  6. pandas-缺失值处理
  7. 20K掌握的技术要点？
  8. FT_Get_Var error on comiling
  9. NAT技术详解
  10. 消息队列的使用&lt;二&gt;：ActiveMQ的基本使用（Java）