神奇的幻方
題目描述
幻方是一種很神奇的NN矩陣：它由數(shù)字1,2,3,……,NN構(gòu)成，且每行、每列及兩條對(duì)角線上的數(shù)字之和都相同竞思。
當(dāng)N為奇數(shù)時(shí)表谊，我們可以通過(guò)以下方法構(gòu)建一個(gè)幻方：
首先將1寫在第一行的中間。
之后盖喷，按如下方式從小到大依次填寫每個(gè)數(shù)K(K=2,3,…,N*N)：
- 若(K?1)在第一行但不在最后一列爆办，則將K填在最后一行，(K?1)所在列的右一列课梳；
- 若(K?1)在最后一列但不在第一行距辆，則將K填在第一列，(K?1)所在行的上一行暮刃；
- 若(K?1)在第一行最后一列跨算，則將K填在(K?1)的正下方；
- 若(K?1)既不在第一行椭懊，也不在最后一列诸蚕，如果(K?1)的右上方還未填數(shù)，則將K填在(K?1)的右上方氧猬，否則將K填在(K?1)的正下方背犯。
現(xiàn)給定N請(qǐng)按上述方法構(gòu)造N*N的幻方。
輸入輸出格式
輸入格式：
輸入文件只有一行盅抚，包含一個(gè)整數(shù)N即幻方的大小漠魏。
輸出格式：
輸出文件包含N行，每行N個(gè)整數(shù)泉哈，即按上述方法構(gòu)造出的N*N的幻方蛉幸。相鄰兩個(gè)整數(shù)之間用單個(gè)空格隔開。
輸入輸出樣例
輸入樣例#1：
3
輸出樣例#1：
8 1 6
3 5 7
4 9 2
思路
無(wú)難度模擬
代碼
#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
int n,x,y;
int mp[200][200];
int main()
{
scanf("%d",&n);
x = 1,y = (n+1)/2;
mp[x][y]=1;
for(int i=2;i<=n*n;i++)
{
if(x==1&&y!=n)
x=n,y++;
else if(x!=1&&y==n)
x--,y=1;
else if(x==1&&y==n)
x++;
else if(!mp[x-1][y+1])
x--,y++;
else
x++;
mp[x][y]=i;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
printf("%d ",mp[i][j]);
printf("\n");
}
}
信息傳遞
題目描述
有n個(gè)同學(xué)（編號(hào)為1到n）正在玩一個(gè)信息傳遞的游戲丛晦。在游戲里每人都有一個(gè)固定的信息傳遞對(duì)象奕纫，其中，編號(hào)為i的同學(xué)的信息傳遞對(duì)象是編號(hào)為Ti同學(xué)烫沙。
游戲開始時(shí)匹层，每人都只知道自己的生日。之后每一輪中锌蓄，所有人會(huì)同時(shí)將自己當(dāng)前所知的生日信息告訴各自的信息傳遞對(duì)象（注意：可能有人可以從若干人那里獲取信息升筏，但是每人只會(huì)把信息告訴一個(gè)人，即自己的信息傳遞對(duì)象）瘸爽。當(dāng)有人從別人口中得知自己的生日時(shí)您访，游戲結(jié)束。請(qǐng)問(wèn)該游戲一共可以進(jìn)行幾輪剪决？
輸入輸出格式
輸入格式：
輸入共2行灵汪。
第1行包含1個(gè)正整數(shù)n表示n個(gè)人檀训。
第2行包含n個(gè)用空格隔開的正整數(shù)T1,T2,……,Tn其中第i個(gè)整數(shù)Ti示編號(hào)為i
的同學(xué)的信息傳遞對(duì)象是編號(hào)為Ti的同學(xué)，Ti≤n且Ti≠i
數(shù)據(jù)保證游戲一定會(huì)結(jié)束享言。
輸出格式：
輸出共 1 行峻凫，包含 1 個(gè)整數(shù)，表示游戲一共可以進(jìn)行多少輪览露。
輸入輸出樣例
輸入樣例#1：52 4 2 3 1
輸出樣例#1：3
說(shuō)明
樣例1解釋
游戲的流程如圖所示荧琼。當(dāng)進(jìn)行完第 3 輪游戲后， 4 號(hào)玩家會(huì)聽到 2 號(hào)玩家告訴他自
己的生日差牛，所以答案為 3命锄。當(dāng)然，第 3 輪游戲后偏化， 2 號(hào)玩家累舷、 3 號(hào)玩家都能從自己的消息
來(lái)源得知自己的生日，同樣符合游戲結(jié)束的條件夹孔。
對(duì)于 30%的數(shù)據(jù)被盈， n ≤ 200；
對(duì)于 60%的數(shù)據(jù)搭伤， n ≤ 2500只怎；
對(duì)于 100%的數(shù)據(jù)， n ≤ 200000怜俐。
思路
找最小環(huán)
先把不可能的人踢了
即：先把入度為0的點(diǎn)刪除身堡，然后把這個(gè)點(diǎn)指向的點(diǎn)的入度-1，如果入度為0拍鲤，也刪去贴谎，這樣就只保留有用的點(diǎn)，那么從任意一個(gè)點(diǎn)開始季稳，用vis數(shù)組記錄是否被訪問(wèn)過(guò)擅这，訪問(wèn)到一個(gè)新節(jié)點(diǎn)就累加計(jì)數(shù)器，然后就做出來(lái)了.bfs和dfs都可以
代碼
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
int to[200010],vis[200010], rubian[200010];
int n,ans;
queue <int> q;
int main()
{
memset(to, 0, sizeof(to));
memset(vis, 0, sizeof(vis));
memset(rubian, 0, sizeof(rubian));
scanf("%d", &n);
ans = n;
for (int i = 1; i <= n; i++)
{
scanf("%d", &to[i]);
++rubian[to[i]];
}
for (int i = 1; i <= n; i++)
if (rubian[i] == 0)
{
q.push(i);
vis[i] = 1;
}
while (!q.empty())
{
int u = q.front();
q.pop();
--rubian[to[u]];
if (rubian[to[u]] == 0)
{
vis[to[u]] = 1;
q.push(to[u]);
}
}
int temp,j;
for (int i = 1; i <= n; i++)
{
if (vis[i] == 0 && rubian[i] != 0)
{
vis[i] = 1;
temp = 1;
j = to[i];
while (!vis[j])
{
vis[j] = 1;
j = to[j];
temp++;
}
if (temp <= ans)
ans = temp;
}
}
printf("%d\n", ans);
return 0;
}
跳石頭
題目描述
這項(xiàng)比賽將在一條筆直的河道中進(jìn)行,河道中分布著一些巨大巖石景鼠。組委會(huì)已經(jīng)選擇好了兩塊巖石作為比賽起點(diǎn)和終點(diǎn)仲翎。在起點(diǎn)和終點(diǎn)之間,有 N 塊巖石(不含起點(diǎn)和終 點(diǎn)的巖石)。在比賽過(guò)程中,選手們將從起點(diǎn)出發(fā),每一步跳向相鄰的巖石,直至到達(dá) 終點(diǎn)铛漓。
為了提高比賽難度,組委會(huì)計(jì)劃移走一些巖石,使得選手們?cè)诒荣愡^(guò)程中的最短跳 躍距離盡可能長(zhǎng)溯香。由于預(yù)算限制,組委會(huì)至多從起點(diǎn)和終點(diǎn)之間移走 M 塊巖石(不能 移走起點(diǎn)和終點(diǎn)的巖石)。
輸入輸出格式
輸入格式：
輸入文件名為 stone.in浓恶。
輸入文件第一行包含三個(gè)整數(shù) L,N,M,分別表示起點(diǎn)到終點(diǎn)的距離,起點(diǎn)和終 點(diǎn)之間的巖石數(shù),以及組委會(huì)至多移走的巖石數(shù)玫坛。
接下來(lái) N 行,每行一個(gè)整數(shù),第 i 行的整數(shù) Di(0 < Di < L)表示第 i 塊巖石與 起點(diǎn)的距離。這些巖石按與起點(diǎn)距離從小到大的順序給出,且不會(huì)有兩個(gè)巖石出現(xiàn)在同 一個(gè)位置包晰。
輸出格式：
輸出文件名為 stone.out湿镀。 輸出文件只包含一個(gè)整數(shù),即最短跳躍距離的最大值禀梳。
輸入輸出樣例
輸入樣例#1：
25 5 2
2
11
14
17
21
輸出樣例#1：
4
思路
我們對(duì)于一個(gè)長(zhǎng)度x，想看看它是否可以符合刪除石頭數(shù)小于等于m肠骆，可以這樣做：
從位置的小到大掃遍所有石頭，用一個(gè)變量存儲(chǔ)上一個(gè)跳到的點(diǎn)塞耕。第一個(gè)與這上一個(gè)點(diǎn)的距離大于等于x的石頭即是下一個(gè)跳到的點(diǎn)蚀腿。這里用了一點(diǎn)貪心的思想：因?yàn)槿绻惶降谝粋€(gè)符合條件的點(diǎn)上，那么整個(gè)隊(duì)列的稀疏度就會(huì)提高扫外，最終需要?jiǎng)h除的石頭也會(huì)更多莉钙。因?yàn)槲覀円∽顑?yōu)狀態(tài)，所以要保證跳過(guò)的石頭數(shù)最少筛谚。當(dāng)然磁玉，如果某個(gè)石頭到終點(diǎn)的距離小于x，那它不能被統(tǒng)計(jì)到——所以得刪去后面這些無(wú)法跳到的石頭驾讲。我自認(rèn)為這應(yīng)該也是一個(gè)坑點(diǎn)（雖然我第一遍就判斷了）蚊伞。
這樣，便求出了這個(gè)x是否可行吮铭，如果可行时迫，那就往右邊二分，但要記得范圍要包括x谓晌；若不行掠拳，則往左邊二分，右限制不包括x纸肉。然后溺欧，二分到左右邊界相等，輸出即可柏肪。
然后此題就做完了姐刁。大家應(yīng)該很容易理解。
代碼
#include<cstdio>
#include<algorithm>
using namespace std;
int sto[100000];//開大一點(diǎn)烦味，保險(xiǎn)
int main()
{
int s,n,m;
scanf("%d%d%d",&s,&n,&m);
int zuo=1,you=s,mid;//所有邊界為1龙填、s
for(int i=0;i<n;i++)scanf("%d",&sto[i]);
sort(sto,sto+n);//從小到大排序
int sg,cnt,ii;
while(zuo!=you)
{
mid=(zuo+you+1)>>1;//位運(yùn)算加速
sg=cnt=0;//初始化
for(ii=0;ii<n;ii++)
{
if(s-sto[ii]<mid)break;//如解析中所述，若再跳x已超過(guò)終點(diǎn)拐叉，則不可取此點(diǎn)岩遗，它后面的也顯然不可取
if(sto[ii]-sg<mid)cnt++;//跳過(guò)
else sg=sto[ii];//貪心，直接跳到
}
cnt+=n-ii;//統(tǒng)計(jì)最后被刪除的點(diǎn)數(shù)
if(cnt<=m)zuo=mid;
else you=mid-1;//二分邊界更新凤瘦，具體請(qǐng)見(jiàn)解析
}
printf("%d",zuo);//輸出
return 0;
}
子串
題目描述
有兩個(gè)僅包含小寫英文字母的字符串 A 和 B∷藿福現(xiàn)在要從字符串 A 中取出 k 個(gè)互不重疊的非空子串,然后把這 k 個(gè)子串按照其在字符串 A 中出現(xiàn)的順序依次連接起來(lái)得到一 個(gè)新的字符串,請(qǐng)問(wèn)有多少種方案可以使得這個(gè)新串與字符串 B 相等?注意:子串取出 的位置不同也認(rèn)為是不同的方案。
輸入輸出格式
輸入格式：
輸入文件名為 substring.in蔬芥。
第一行是三個(gè)正整數(shù) n,m,k,分別表示字符串 A 的長(zhǎng)度,字符串 B 的長(zhǎng)度,以及問(wèn)
題描述中所提到的 k,每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開梆靖。 第二行包含一個(gè)長(zhǎng)度為 n 的字符串,表示字符串 A控汉。 第三行包含一個(gè)長(zhǎng)度為 m 的字符串,表示字符串 B。
輸出格式：
輸出文件名為 substring.out返吻。 輸出共一行,包含一個(gè)整數(shù),表示所求方案數(shù)姑子。由于答案可能很大,所以這里要求[b]輸出答案對(duì) 1,000,000,007 取模的結(jié)果。[/b]
輸入輸出樣例
輸入樣例#1：
6 3 1
aabaab
aab
輸出樣例#1：
2
輸入樣例#2：
6 3 2
aabaab
aab
輸出樣例#2：
7
輸入樣例#3：
6 3 3
aabaab
aab
輸出樣例#3：
7
說(shuō)明
對(duì)于第 1 組數(shù)據(jù):1≤n≤500,1≤m≤50,k=1;
對(duì)于第 2 組至第 3 組數(shù)據(jù):1≤n≤500,1≤m≤50,k=2;
對(duì)于第 4 組至第 5 組數(shù)據(jù):1≤n≤500,1≤m≤50,k=m;
對(duì)于第 1 組至第 7 組數(shù)據(jù):1≤n≤500,1≤m≤50,1≤k≤m;
對(duì)于第 1 組至第 9 組數(shù)據(jù):1≤n≤1000,1≤m≤100,1≤k≤m;
對(duì)于所有 10 組數(shù)據(jù):1≤n≤1000,1≤m≤200,1≤k≤m测僵。
思路
最后數(shù)組壓到二維的就可以省空間了街佑。
代碼
//不壓維
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 1000 + 5, maxm = 200 + 5, moder = 1000000007;
int m, n, K;
char stra[maxn], strb[maxm];
int f[maxn][maxm][maxm], s[maxn][maxm][maxm];
void solve() {
s[0][0][0] = 1;
for(int i = 1; i <= n; ++i) {
s[i][0][0] = 1; //注意如果不壓到二維，這是需要的
for(int j = 1; j <= m; ++j)
if(stra[i-1] == strb[j-1]) {
for(int k = 1; k <= min(K, j); ++k) {
f[i][j][k] = (s[i-1][j-1][k-1] + f[i-1][j-1][k]) % moder,
s[i][j][k] = (s[i-1][j][k] + f[i][j][k]) % moder;
}
}else for (int k = 1; k <= min(K, j); ++k) s[i][j][k] = s[i-1][j][k]; //注意如果不壓到二維，這是需要的
}
printf("%d\n", s[n][m][K]);
}
int main() {
scanf("%d%d%d%s%s", &n, &m, &K, stra, strb);
solve();
return 0;
}
//壓維
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 1000 + 5, maxm = 200 + 5, moder = 1000000007;
int m, n, K;
char stra[maxn], strb[maxm];
int f[maxm][maxm], s[maxm][maxm];
void solve() {
s[0][0] = 1;
for(int i = 1; i <= n; ++i) {
for(int j = m; j > 0; --j)
if(stra[i-1] == strb[j-1]) {
for(int k = min(K, j); k > 0; --k) {
f[j][k] = (s[j-1][k-1] + f[j-1][k]) % moder,
s[j][k] = (s[j][k] + f[j][k]) % moder;
}
}else fill(f[j], f[j] + min(K, j) + 1, 0);
}
printf("%d\n", s[m][K]);
}
int main() {
scanf("%d%d%d%s%s", &n, &m, &K, stra, strb);
solve();
return 0;
}
斗地主
題目描述
牛牛最近迷上了一種叫斗地主的撲克游戲。斗地主是一種使用黑桃壁袄、紅心惊完、梅花、方片的A到K加上大小王的共54張牌來(lái)進(jìn)行的撲克牌游戲。在斗地主中，牌的大小關(guān)系根據(jù)牌的數(shù)碼表示如下：3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王，而花色并不對(duì)牌的大小產(chǎn)生影響谊迄。每一局游戲中，一副手牌由n張牌組成烟央。游戲者每次可以根據(jù)規(guī)定的牌型進(jìn)行出牌鳞上，首先打光自己的手牌一方取得游戲的勝利。
現(xiàn)在吊档，牛牛只想知道篙议，對(duì)于自己的若干組手牌，分別最少需要多少次出牌可以將它們打光怠硼。請(qǐng)你幫他解決這個(gè)問(wèn)題鬼贱。
需要注意的是，本題中游戲者每次可以出手的牌型與一般的斗地主相似而略有不同香璃。
具體規(guī)則如下：
輸入輸出格式
輸入格式：
第一行包含用空格隔開的2個(gè)正整數(shù)T和n这难，表示手牌的組數(shù)以及每組手牌的張數(shù)。
接下來(lái)T組數(shù)據(jù)葡秒，每組數(shù)據(jù)n行姻乓，每行一個(gè)非負(fù)整數(shù)對(duì)aibi表示一張牌，其中ai示牌的數(shù)碼眯牧，bi表示牌的花色蹋岩，中間用空格隔開。特別的学少，我們用1來(lái)表示數(shù)碼A剪个，11表示數(shù)碼J，12表示數(shù)碼Q版确，13表示數(shù)碼K扣囊；黑桃乎折、紅心、梅花侵歇、方片分別用1-4來(lái)表示骂澄；小王的表示方法為01，大王的表示方法為02惕虑。
輸出格式：
共T行坟冲，每行一個(gè)整數(shù)，表示打光第i手牌的最少次數(shù)枷遂。
輸入輸出樣例
輸入樣例#1：
1 8
7 4
8 4
9 1
10 4
11 1
5 1
1 4
1 1
輸出樣例#1：
3
思路
搜索+剪枝
忽略花色，統(tǒng)計(jì)每種碼數(shù)出現(xiàn)次數(shù)方便出牌棋嘲。
每次都先出順子酒唉，對(duì)于手中剩下的牌我們貪心地將剩下的組合牌需要打的次數(shù)計(jì)算出來(lái)，然后更新ans以剪枝沸移。
雙王算作對(duì)牌痪伦。順子不包括2和雙王。
代碼
#include<cstdio>
#include<cstring>
#define FOR(a,b,c) for(int a=(b);a<=(c);a++)
using namespace std;
const int N = 25;
int a[N],c[N];
int n,T,ans;
int Qans() {
memset(c,0,sizeof(c));
FOR(i,0,13) c[a[i]]++;
int tot=0; //tot帶牌
while(c[4]&&c[2]>1) c[4]--,c[2]-=2,tot++;
while(c[4]&&c[1]>1) c[4]--,c[1]-=2,tot++;
while(c[4]&&c[2]) c[4]--,c[2]--,tot++;
while(c[3]&&c[2]) c[3]--,c[2]--,tot++;
while(c[3]&&c[1]) c[3]--,c[1]--,tot++;
return tot+c[1]+c[2]+c[3]+c[4]; //帶牌+三張 對(duì)子 單張
}
void dfs(int now) {
if(now>=ans) return ;
int tmp=Qans();
if(now+tmp<ans) ans=now+tmp;
FOR(i,2,13) { //三順子
int j=i;
while(a[j]>=3) j++;
if(j-i>=2) {
FOR(j2,i+1,j-1) {
FOR(k,i,j2) a[k]-=3;
dfs(now+1);
FOR(k,i,j2) a[k]+=3;
}
}
}
FOR(i,2,13) { //雙順子
int j=i;
while(a[j]>=2) j++;
if(j-i>=3) {
FOR(j2,i+2,j-1) {
FOR(k,i,j2) a[k]-=2;
dfs(now+1);
FOR(k,i,j2) a[k]+=2;
}
}
}
FOR(i,2,13) { //單順子
int j=i;
while(a[j]>=1) j++;
if(j-i>=5) {
FOR(j2,i+4,j-1) {
FOR(k,i,j2) a[k]--;
dfs(now+1);
FOR(k,i,j2) a[k]++;
}
}
}
}
int main() {
//freopen("in.in","r",stdin);
//freopen("out.out","w",stdout);
scanf("%d%d",&T,&n);
while(T--) {
memset(a,0,sizeof(a));
int x,y;
FOR(i,1,n) {
scanf("%d%d",&x,&y);
if(x==1) x=13; else if(x) x--;
a[x]++;
}
ans=1e9;
dfs(0);
printf("%d\n",ans);
}
return 0;
}
