国产99久久精品_欧美日本韩国一区二区_激情小说综合网_欧美一级二级视频_午夜av电影_日本久久精品视频

最新文章專題視頻專題問答1問答10問答100問答1000問答2000關鍵字專題1關鍵字專題50關鍵字專題500關鍵字專題1500TAG最新視頻文章推薦1 推薦3 推薦5 推薦7 推薦9 推薦11 推薦13 推薦15 推薦17 推薦19 推薦21 推薦23 推薦25 推薦27 推薦29 推薦31 推薦33 推薦35 推薦37視頻文章20視頻文章30視頻文章40視頻文章50視頻文章60 視頻文章70視頻文章80視頻文章90視頻文章100視頻文章120視頻文章140 視頻2關鍵字專題關鍵字專題tag2tag3文章專題文章專題2文章索引1文章索引2文章索引3文章索引4文章索引5123456789101112131415文章專題3
問答文章1 問答文章501 問答文章1001 問答文章1501 問答文章2001 問答文章2501 問答文章3001 問答文章3501 問答文章4001 問答文章4501 問答文章5001 問答文章5501 問答文章6001 問答文章6501 問答文章7001 問答文章7501 問答文章8001 問答文章8501 問答文章9001 問答文章9501
當前位置: 首頁 - 科技 - 知識百科 - 正文

codeforcesRound#260(div2)D解題報告

來源:懂視網 責編:小采 時間:2020-11-09 08:01:20
文檔

codeforcesRound#260(div2)D解題報告

codeforcesRound#260(div2)D解題報告:D. A Lot of Games time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Andrew, Fedor and Alex are inventive guys. Now they invent the game with strings for two players. Given a group
推薦度:
導讀codeforcesRound#260(div2)D解題報告:D. A Lot of Games time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Andrew, Fedor and Alex are inventive guys. Now they invent the game with strings for two players. Given a group

解法:

首先存這些字符,用trie來存,通過trie就很容易聯想到樹型DP,這里的DP就不是取最優值之類的了,而是用來弄到達某個節點的勝負情況。

我們首先設節點v,win[v]代表已經組裝好的字符剛好匹配到v了,然后需要進行下一步匹配時,先手是否可以贏,lose[v]則代表先手是否會輸。

葉節點,win[v] = false, lose[v] = true.

其他節點 win[v] = win[v] | !win[child], lose[v] = lose[v] | !lose[child]. (因為每次贏的人,下一個就不是先手,所以結果肯定是跟下一個節點的贏成對立關系)。


如若win[0] = true , lose[0] = true則意味著第一局的人可以操控結果,否則按照k的次數來判斷是否可以贏。

代碼:

#include 
#include 
#define N_max 123456
#define sigma_size 26

using namespace std;

bool win[N_max], lose[N_max];
int n, k;
char st1[N_max];

class Trie{
public:
	int ch[N_max][sigma_size];
	int sz;

	Trie() {
	sz=0;
	memset(ch[0], 0, sizeof(ch[0]));
	}

	int idx(char c) {
	return c-'a';
	}

	void insert(char *s) {
	int l = strlen(s), u = 0;

	for (int i = 0; i < l; i++) {
	int c = idx(s[i]);

	if (!ch[u][c]) {
	ch[u][c] = ++sz;
	memset(ch[sz], 0, sizeof(ch[sz]));
	}

	u = ch[u][c];
	}
	}
};

Trie T;

void init() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++) {
	scanf("%s", st1);
	T.insert(st1);
	}
}

void dfs(int v) {
	bool is_leaf = true;

	win[v] = false;
	lose[v] = false;

	for (int i = 0; i < sigma_size; i++) {
	int tmp = T.ch[v][i];

	if (tmp) {
	is_leaf = false;
	dfs(T.ch[v][i]);
	win[v] |= !win[T.ch[v][i]];
	lose[v] |= !lose[T.ch[v][i]];
	}
	}

	if (is_leaf) {
	win[v] = false;
	lose[v] = true;
	}
}

void ans(bool res) {
	puts(res? "First":"Second");
}

void solve() {
	dfs(0);

	if (win[0] && lose[0])
	ans(true);
	else if (win[0])
	ans(k&1);
	else
	ans(0);
}

int main() {
	init();
	solve();
}

聲明:本網頁內容旨在傳播知識,若有侵權等問題請及時與本網聯系,我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com

文檔

codeforcesRound#260(div2)D解題報告

codeforcesRound#260(div2)D解題報告:D. A Lot of Games time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Andrew, Fedor and Alex are inventive guys. Now they invent the game with strings for two players. Given a group
推薦度:
標簽: 報告 解題 round
  • 熱門焦點

最新推薦

猜你喜歡

熱門推薦

專題
Top
主站蜘蛛池模板: 黄色在线观看视频网站 | 欧美日韩亚洲高清不卡一区二区三区 | 精品视频一区二区三区 | 国产欧美在线视频免费 | 手机国产精品一区二区 | 国产精品糟蹋漂亮女教师 | 欧美精品午夜久久久伊人 | 国内精品久久久久久中文字幕 | 久久久成人网 | 亚洲欧洲国产成人综合一本 | 免费一区二区 | 视频精品一区二区三区 | 黑人粗又大 | 国产欧美一区二区三区在线 | 国产在线播放网站 | 亚洲欧美精选 | 最新国产精品精品视频 | 欧美日韩福利视频 | 日韩欧美视频 | 在线观看亚洲欧美 | 欧美日韩亚洲无线码在线观看 | 极品毛片 | 91精品国产91热久久p | 亚洲福利在线观看 | 精品伊人 | 久久久青青久久国产精品 | 亚洲一区二区三区久久久久 | 精品久久久久中文字幕日本 | 国产成人在线精品 | 国产精品成人久久久久 | 国产日产高清欧美一区二区三区 | 日韩综合 | 欧美日韩亚洲无线码在线观看 | 黄色免费网站视频 | 精品日韩一区二区三区视频 | 欧美在线一区二区三区精品 | 国产精品亚洲一区二区三区 | 欧美极品尤物在线播放一级 | 亚洲清纯自偷自拍另类专区 | 日韩经典第一页 | 亚洲国产精品一区二区久久 |