简单题，反正菜
Dasha Code Championship - SPb Finals Round (only for onsite-finalists)
A. Anadi and Domino
https://codeforces.com/problemset/problem/1210/A
思路：当Grape中节点个数少于等于6个时，最多存在15条边，每个节点赋值一个点数，所以n <= 6 时,可存在变数为m，当Grape中节点的个数为7个时，必然是存在俩个节点属于同一标记的，因此枚举每俩个节点,
如果其他节点和这俩个节点同时存在边，则这条边必然是不可取的，因为各种类型的筛子只能取一个，所以需要减去
/*
* @Author: CY__HHH
* @Date: 2019-10-21 12:09:09
* @LastEditTime: 2019-10-21 12:09:09
*/
#include<bits/stdc++.h>
#define inf (0x3f3f3f3f)
typedef long long i64;
using namespace std;
const int maxn = 32;
bool Grape[maxn][maxn];
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n,m,u,v; cin >> n >> m;
for(int i=0;i!=m;++i)
{
cin >> u >> v;
Grape[u][v] = Grape[v][u] = true;
}
int minn = inf;
if( n <= 6)
cout << m <<'
';
else{
for(int i=1;i<=n;++i)
{
for(int j=i+1;j<=n;++j)
{
int cnt = 0;
for(int k=1;k<=n;++k)
if(Grape[i][k]&&Grape[j][k])
++cnt;
minn = min(minn,cnt);
}
}
cout << m - minn << '
';
}
return 0;
}
Codeforces Round #516 (Div. 1, by Moscow Team Olympiad) B. Labyrinth
https://codeforces.com/contest/1063/problem/B
思路：记忆化bfs，因为搜索的节点的左右移的个数是有限的，因此可能先搜索到的节点并不是最优的，因此如果存在更好的状态就更新
#include<bits/stdc++.h>
#define inf (0x3f3f3f3f)
using namespace std;
const int maxn = 2e3 + 32;
char Grape[maxn][maxn];
int n,m,r,c,lt,rt;
int dis[maxn][maxn];
bool vis[maxn][maxn];
queue<pair<int,int> > q;
int arr[][4] = {1,-1,0,0,
0,0,1,-1};
int main()
{
ios::sync_with_stdio(false); cin.tie(0),cout.tie(0);
cin>>n>>m>>r>>c>>lt>>rt;
--r,--c;
for(int i=0;i!=n;++i)
cin>>Grape[i];
memset(dis,inf,sizeof(dis));
dis[r][c] = 0;
q.push(make_pair(r,c));
while(!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
for(int i=0;i!=4;++i)
{
int nx = x + arr[0][i];
int ny = y + arr[1][i];
if(nx>=0&&nx<n&&ny>=0&&ny<m&&Grape[nx][ny]=='.')
{
if(i==3)
{
if(dis[nx][ny] > dis[x][y] + 1)
{
dis[nx][ny] = dis[x][y] + 1;
q.push(make_pair(nx,ny));
}
}
else
{
if(dis[nx][ny] > dis[x][y])
{
dis[nx][ny] = dis[x][y];
q.push(make_pair(nx,ny));
}
}
}
}
}
int cnt = 0;
for(int i=0;i!=n;++i)
for(int j=0;j!=m;++j)
{
if(dis[i][j] == inf)
continue;
int l = dis[i][j];
int r = j + l - c;
if(l<=lt&&r<=rt)
++cnt;
}
cout << cnt <<'
';
}
Codeforces Round #562 (Div. 2) B. Pairs
https://codeforces.com/problemset/problem/1169/B
思路：先枚举下是否有没有相同的俩对节点，如果存在，则必定得从这俩对中各自取一个，枚举下就好了
#include<bits/stdc++.h> using namespace std; const int maxn = 3e5 + 32; int a[maxn],b[maxn],c[2],d[2]; int main() { int n,m; scanf("%d%d",&n,&m); scanf("%d%d",&a[0],&b[0]); c[0] = a[0],c[1] = b[0]; bool flag = false; for(int i=1;i!=m;++i) { scanf("%d%d",&a[i],&b[i]); if(a[i]!=c[0]&&a[i]!=c[1]&&b[i]!=c[0]&&b[i]!=c[1]) { flag = true; d[0] = a[i],d[1] = b[i]; } } if(!flag) { printf("YES "); return 0; } for(int i=0;i!=2;++i) { for(int j=0;j!=2;++j) { flag = true; for(int k=0;k!=m;++k) { if(a[k]!=c[i]&&a[k]!=d[j]&&b[k]!=c[i]&&b[k]!=d[j]) { flag = false; break; } } if(flag) { printf("YES "); return 0; } } } printf("NO "); }
https://codeforces.com/problemset/problem/1133/F1
Codeforces Round #544 (Div. 3) F1. Spanning Tree with Maximum Degree
求图中节点度最大的生成树，则找出度最大的节点，由节点bfs就好了
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 32;
bool vis[maxn];
int du[maxn];
vector<int> Grape[maxn];
int main()
{
int n,m,u,v,pos,maxx = 0; scanf("%d%d",&n,&m);
for(int i=0;i!=m;++i)
{
scanf("%d%d",&u,&v);
++du[u],++du[v];
if(du[u] > maxx)
{
maxx = du[u];
pos = u;
}
if(du[v] > maxx)
{
maxx = du[v];
pos = v;
}
Grape[u].push_back(v);
Grape[v].push_back(u);
}
queue<int> q; q.push(pos);
vis[pos] = true;
while(!q.empty())
{
int cur = q.front(); q.pop();
for(int i=0;i!=Grape[cur].size();++i)
{
int v = Grape[cur][i];
if(vis[v])
continue;
printf("%d %d
",cur,v);
q.push(v);
vis[v] = true;
}
}
}
Codeforces Round #485 (Div. 1)A. Fair
成功贡献一发TLE后发现我不愧是和傻子
思路：因为颜色的种类情况很少，所以拿空间换时间呐，dist[node][type] 表示node节点到type需要的最少步数,将每种类型广搜就好了
/*
* @Author: CY__HHH
* @Date: 2019-10-21 12:09:09
* @LastEditTime: 2019-10-22 19:11:12
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 32;
bool vis[maxn];
typedef long long i64;
int main()
{
ios::sync_with_stdio(false); cin.tie(0),cout.tie(0);
int n,m,s,k,u,v; cin>>n>>m>>s>>k;
vector<int> col(n+1);
for(int i=1;i<=n;++i)
cin >> col[i];
vector<vector<int>> Grape(n+1);
for(int i=1;i<=m;++i)
{
cin >> u >> v;
Grape[u].push_back(v);
Grape[v].push_back(u);
}
vector<vector<int>> dist(n+1);
for(int i=1;i<=n;++i)
dist[i].resize(s+1);
for(int type = 1;type <= s;++type)
{
memset(vis,false,sizeof(vis));
queue<int> seq;
for(int i=1;i<=n;++i)
{
if(col[i] == type)
{
seq.push(i);
dist[i][type] = 0;
vis[i] = true;
}
}
while(!seq.empty())
{
int cur = seq.front();
seq.pop();
for(auto v:Grape[cur])
{
if(vis[v])
continue;
dist[v][type] = dist[cur][type] + 1;
seq.push(v);
vis[v] = true;
}
}
}
for(int i=1;i<=n;++i)
{
i64 sum = 0;
sort(dist[i].begin()+1,dist[i].end());
for(int j=1;j<=k;++j)
sum += dist[i][j];
cout<<sum<<" ";
}
cout<<'
';
}
附上一道二分题
https://codeforces.com/problemset/problem/1251/D
贪心的策略，先将l排个序，low 为 0,high 为 1e9 + 5,去二分查找是否存在某个值mid，使得排序后的数组一定是距离mid 最近的 ，如果对应的r大于mid则sum += max(0,mid - l)
如果存在一半个，并且sum和小于等于S，则说明可行
/*
* @Author: CY__HHH
* @Date: 2019-10-26 13:38:55
* @LastEditTime: 2019-10-26 17:49:26
*/
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0;i!=n;++i)
#define per(i, n) for(int i=n-1;i>=0;--i)
#define Rep(i, sta, n) for(int i=sta;i!=n;++i)
#define rep1(i, n) for(int i=1;i<=n;++i)
#define per1(i, n) for(int i=n;i>=1;--i)
#define Rep1(i, sta, n) for(int i=sta;i<=n;++i)
#define L k<<1
#define R k<<1|1
#define inf (0x3f3f3f3f)
#define llinf (1e18)
#define mid (tree[k].l+tree[k].r)>>1
#define ALL(A) A.begin(),A.end()
#define SIZE(A) ((int)A.size())
typedef long long i64;
using namespace std;
typedef struct Node{
int l,r;
bool operator<(const struct Node& no)const
{
return l < no.l;
}
}node;
int n,Count;
i64 s;
vector<node> arr;
bool find(int Mid)
{
i64 sum = 0;
for(auto& v:arr)
sum += v.l;
int cnt = 0;
for(int i=n-1;i>=0&&cnt<Count;--i)
{
if(arr[i].r >= Mid)
{
sum += max(0,Mid - arr[i].l);
++cnt;
}
}
return cnt == Count&&sum <= s;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int t; cin>>t;
while(t--)
{
cin>>n>>s;
arr.resize(n);
Count = (n + 1) >> 1;
for(auto& v:arr)
cin>>v.l>>v.r;
sort(arr.begin(),arr.end());
int low = 0,high = 1e9 + 4 ,ans;
while(low <= high)
{
int Mid = (low + high) >> 1;
if(find(Mid))
{
ans = Mid;
low = Mid + 1;
}
else
high = Mid - 1;
}
cout<<ans<<'
';
}
return 0;
}