Codeforces 907 矩阵编号不相邻构造 团操作状压DFS
2024-09-05 19:37:00
A.
#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#define pb push_back
#define inf 1e9
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que;
const double eps = 1.0e-8;
typedef pair<int, int> pairint;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e6 + ;
const int maxm = ;
const int turn[][] = {{, }, { -, }, {, }, {, -}};
//next_permutation
ll mod = 1e9 + ;
int main()
{
//freopen("out1.txt", "w", stdout);
int v1, v2, v3, vm;
int anser;
cin >> v1 >> v2 >> v3 >> vm;
int flag = ;
if (vm >= v2)
{
cout << - << endl;
exit();
}
for (int i = v3; i <= * v3; i++)
{
if (i >= vm && i <= * vm)
{
flag = ;
anser = i;
break;
}
}
if (flag)
{
cout << * v1 << endl;
cout << * v2 << endl;
cout << anser << endl;
}
else
{
cout << - << endl;
}
}
B.
#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#define pb push_back
#define inf 1e9
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que;
const double eps = 1.0e-8;
typedef pair<int, int> pairint;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e6 + ;
const int maxm = ;
const int turn[][] = {{, }, { -, }, {, }, {, -}};
//next_permutation
ll mod = 1e9 + ;
char f[][];
bool judge(int x)
{
int flag = ;
int cur = (x - ) / ;
x = x % ;
if (x == )
{
x = ;
}
int cur1 = x - ;
// cout << "y" << " " << cur1 * 3 + 1 << " " << cur1 * 3 + 3 << endl;
// cout << "x" << " " << cur * 3 + 1 << " " << cur * 3 + 3 << endl;
for (int i = cur * + ; i <= cur * + ; i++)
{
for (int j = cur1 * + ; j <= cur1 * + ; j++)
{
if (f[i][j] == '.')
{
f[i][j] = '!';
flag = ;
}
}
}
if (flag)
{
return false;
}
else
{
for (int i = ; i <= ; i++)
{
for (int j = ; j <= ; j++)
{
if (f[i][j] == '.')
{
f[i][j] = '!';
}
}
}
return true;
}
}
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out1.txt", "w", stdout);
char now;
for (int i = ; i <= ; i++)
{
for (int j = ; j <= ; j++)
{
scanf("%c", &now);
if (now != '.' && now != 'x' && now != 'o')
{
j--;
}
else
{
f[i][j] = now;
}
}
}
int x, y;
cin >> x >> y;
x = x % ;
if (x == )
{
x = ;
}
y = y % ;
if (y == )
{
y = ;
}
int want = (x - ) * + y;
//cout << want << endl;
judge(want);
for (int i = ; i <= ; i++)
{
for (int j = ; j <= ; j++)
{
cout << f[i][j];
if (j % == && j % != )
{
cout << " ";
}
if (j % == )
{
cout << endl;
}
}
if (i % == )
{
cout << endl;
}
}
}
C.
#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#define pb push_back
#define inf 1e9
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que;
const double eps = 1.0e-8;
typedef pair<int, int> pairint;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e6 + ;
const int maxm = ;
const int turn[][] = {{, }, { -, }, {, }, {, -}};
//next_permutation
ll mod = 1e9 + ;
int flag = ;
int cur = ;
char letter = '.';
int num[];
int test[];
unordered_set<char> ans;
int main()
{
//freopen("out1.txt", "w", stdout);
ios::sync_with_stdio();
cin.tie();
cout.tie(); int n;
int anser = ;
cin >> n;
char a;
string b;
for (int i = ; i < ; i++)
{
ans.insert('a' + i);
}
for (int i = ; i <= n; i++)
{
cin >> a >> b;
if (ans.size() == )
{
if (a == '!')
{
anser++;
}
else if (a == '?')
{
if (b[] == letter)
{
break;
}
else if(!ans.count(b[]))
{
anser++;
}
}
continue;
}
if (a == '!')
{ unordered_set<char> now;
for (char j : b)
{
now.insert(j);
}
for (auto it = ans.begin(); it != ans.end();)
{
if (!now.count(*it))
{
ans.erase(it++);
}
else
{
it++;
}
}
}
else
{
for (char j : b)
{
ans.erase(j);
}
}
}
cout << anser << endl;
}
D.给你一个N*M的矩阵 每位的编号为(i-1)*m+j 要求你重新排列 使得重新排列后每个数与原来相邻的数互不相邻 不存在则输出-1
#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#define pb push_back
#define inf 1e9
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que;
const double eps = 1.0e-8;
typedef pair<int, int> pairint;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e6 + ;
const int maxm = ;
const int turn[][] = {{, }, { -, }, {, }, {, -}};
//next_permutation
ll mod = 1e9 + ;
int n, m;
int ans[];
int pop = ;
int now[];
int f[][];
int num[][];
int cur[][];
int flagf = ;
stack<int> s;
void dfs(int x, int y)
{
if (x == n * m + )
{
flagf = ;
for (int i = n; i >= ; i--)
{
for (int j = m; j >= ; j--)
{
s.push(cur[i][j]);
}
}
return ;
}
if (flagf)
{
return ;
}
int aimx = (x - ) / m + ;
int aimy = (x - ) % m + ;
for (int i = ; i <= n * m; i++)
{
if ((y & ( << i)) == )
{
if ((!num[cur[aimx - ][aimy]][i]) && (!num[cur[aimx][aimy - ]][i]))
{
int numcur = y | ( << i);
//cout << aimx << " " << aimy << " " << i << endl;
cur[aimx][aimy] = i;
dfs(x + , numcur);
}
}
}
}
void solve()
{
for (int i = ; i <= n; i++)
{
for (int j = ; j <= m; j++)
{
f[i][j] = (i - ) * m + j;
}
}
for (int i = ; i <= n; i++)
{
for (int j = ; j <= m; j++)
{
for (int k = ; k <= ; k++)
{
int dx = i + turn[k][];
int dy = j + turn[k][];
if (f[dx][dy] != )
{
num[f[i][j]][f[dx][dy]] = num[f[dx][dy]][f[i][j]] = ;
}
} }
}
dfs(, );
if (flagf)
{
cout << "YES" << endl;
for (int i = ; i <= n; i++)
{
for (int j = ; j <= m; j++)
{
cout << s.top() << " ";
s.pop();
}
cout << endl;
}
}
else
{
cout << "NO" << endl;
}
}
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out1.txt", "w", stdout);
while (cin >> n >> m)
{
if (n <= && m <= )
{
solve();
exit();
}
if (n < m)
{
printf("YES\n");
for (int i = ; i <= n; i++)
{
if (i & )
{
for (int j = (i - ) * m + ; j <= i * m; j += )
{
cout << j << " ";
}
for (int j = (i - ) * m + ; j <= i * m; j += )
{
cout << j << " ";
}
cout << endl;
}
else
{
for (int j = (i - ) * m + ; j <= i * m; j += )
{
cout << j << " ";
}
for (int j = (i - ) * m + ; j <= i * m; j += )
{
cout << j << " ";
}
cout << endl;
}
}
}
else
{
printf("YES\n");
for (int i = ; i <= m; i++)
{
if (i & )
{
now[i] = ;
}
else
{
now[i] = ;
}
}
for (int i = ; i <= n; i++)
{
for (int j = ; j <= m; j++)
{
ans[pop++] = (now[j] - ) * m + j;
now[j] += ;
if (now[j] > n)
{
now[j] = (j & ) + ;
}
//cout<<now[j]<<endl;
}
}
for (int i = ; i < pop; i++)
{
printf("%d", ans[i]);
if (i % m == )
{
printf("\n");
}
else
{
printf(" ");
}
}
}
}
}
E.状压DFS
#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#define pb push_back
#define inf 1e9
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que;
const double eps = 1.0e-8;
typedef pair<int, int> pairint;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e6 + ;
const int maxm = ;
const int turn[][] = {{, }, { -, }, {, }, {, -}};
//next_permutation
ll mod = 1e9 + ;
int n, m;
int num[][];
stack<int> cur, ans;
int anser = ;
void dfs(int now)
{
if (cur.size() >= ans.size())
{
return ;
}
if (now == n)
{
for (int i = ; i < n; i++)
{
if (num[n][i] != ( << n) - )
{
return ;
}
}
ans = cur;
return ;
}
memcpy(num[now + ], num[now], sizeof(num[now]));
dfs(now + );
for (int i = ; i < n; i++)
{
if (( << i) & num[now][now])
{
num[now + ][i] |= num[now][now];
}
}
cur.push(now);
dfs(now + );
cur.pop();
}
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out1.txt", "w", stdout);
cin >> n >> m;
int pa, pb;
for (int i = ; i < n; i++)
{
num[][i] = << i;
//cout<<p[i]<<endl;
ans.push(i);
}
for (int i = ; i <= m; i++)
{
scanf("%d %d", &pa, &pb);
pa--, pb--;
num[][pa] |= << pb;
num[][pb] |= << pa;
}
//pf();
dfs();
cout << ans.size() << endl;
while (!ans.empty())
{
cout << ans.top() + << " ";
ans.pop();
}
cout << endl;
}
最新文章
- Tomcat 7.0的配置
- Opennms 问题整理
- Sql Server数据库之通过SqlBulkCopy快速插入大量数据
- jquery插件colortip（tooltip类型）
- UVALive 6190 Beautiful Spacing (2012 Tokyo regional)
- Oracle开启监听缓慢问题
- RocketMQ
- ssh-keygen的学习总结
- GoogLeNet 解读
- Centos Linux 下Pycharm 安装
- DispatcherServlet 的创建过程
- C++面试基础知识
- python tkinter-窗体
- [BUG]数据库日期格式, 到页面是毫秒值
- Hibernate在PostgreSQL上执行sum函数导致数据失真的问题
- Android Studio入门指南 (历上最全，全球首发)
- ios开发之--UITextField光标右移
- 导出cnblogs文章
- jquery3.0移除了.load()方法
- ipmi监控主机