A - Kefa and Park
题意：就是一棵树，然后本人的家在根上，餐厅在叶子节点上。然后在前往叶子结点的餐厅的时候，途中的结点上有猫，而这个人特别怕毛，如果猫超过M只，那么他就不会走这条路！最终要你输出他能去餐厅的数量，也就是多少条路！
思路：这个题题意很明显，用的是dfs暴力即 可
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+6;
int flag[maxn];//用来标记是否有猫；
vector<int>a[maxn];
int n,m,ans=0;
void dfs(int u,int num,int fa)
{
for (int i = 0;i<a[u].size();i++)
{
int v = a[u][i];
if (v==fa)
continue;
if (flag[v]==0)
{
if (a[v].size()==1)
ans++;
dfs(v,0,u);
}
else if (num+1<=m)
{
if (a[v].size()==1)
ans++;
dfs(v,num+flag[v],u);
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for (int i = 1;i<=n;i++)
scanf("%d",&flag[i]);
for (int i = 1;i<n;i++)//用vector存无权图
{
int u,v;
scanf("%d%d",&u,&v);
a[u].push_back(v);
a[v].push_back(u);
}
dfs(1,flag[1],-1);
printf("%d\n",ans);
}
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 1e6+10;
int N,M;
vector<int> ve[maxn];
int set[4],tag[maxn];
bool push(int x,int id){
int sum = 0;
for(auto v:ve[x]){
if(v>=x) continue;
else if(tag[v] == id) return false;
else sum++;
}
if(sum != x-1-set[id]) return false;
return true;
}
void DFS(int u){
if(u == N+1){
if(set[1] == 0 || set[2] == 0 || set[3] == 0){
cout<<-1<<endl;
}else{
for(int i = 1;i<=N;i++) printf("%d ",tag[i]);
}
exit(0);
}else{
int pushok = 0;
for(int id = 1;id<=3;id++){
if(push(u,id)){
pushok = 1;
tag[u] = id;
set[id]++;
DFS(u+1);
}
}
if(pushok == 0){
cout<<-1<<endl;
exit(0);
}
}
}
int main(){
cin>>N>>M;
int a,b;
for(int _ = 0;_<M;_++){
scanf("%d%d",&a,&b);
ve[a].push_back(b);
ve[b].push_back(a);
}
DFS(1);
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll maxn = 1e6+10;
const ll inf = 1e14;
int N;
ll arr[maxn];
vector<ll> ve[maxn];
ll dis[300][300],edge[300][300];
ll floyd(){
ll res = inf;
for(int k = 0;k<N;k++){
for(int i = 0;i<N;i++){
for(int j = 0;j<N;j++){
if(i == j || j == k || k == i) continue;
res = min(res,dis[i][j]+edge[i][k]+edge[k][j]);
}
}
for(int i =0;i<N;i++){
for(int j = 0;j<N;j++){
dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
if(res == inf) return -1;
else return res;
}
int main(){
cin>>N;
for(int i = 0;i<N;i++){
scanf("%lld",&arr[i]);
if(arr[i] == 0){
i--;
N--;
}
}
if(N>128) cout<<3<<endl;
else{
for(int i = 0;i<N;i++){
for(int j = 0;j<N;j++){
if(arr[i]&arr[j] && i!=j){
dis[i][j] = edge[i][j] = 1;
}else{
dis[i][j] = edge[i][j] = inf;
}
}
}
cout<<floyd()<<endl;
}
return 0;
}
D - Alex and a Rhombus
思路：看图找规律就行了
#include<stdio.h>
int main()
{
int n;
scanf("%d",&n);
printf("%d\n",(n*n + (n - 1)* (n - 1)));
return 0;
}
E - Nick and Array
就是每个数可以执行一种操作，然后的话求如何使乘积最大！
#include<bits/stdc++.h>
#define maxn 100000+10
using namespace std;
struct node
{
int num;
int dis;
} a[maxn];
int cmp1(struct node a,struct node b)
{
return a.num < b.num;
}
int cmp2(struct node a,struct node b)
{
return a.dis<b.dis;
}
int main()
{
int n;
while(cin>>n)
{
for(int i=0; i<n; i++)
{
cin>>a[i].num;
if(a[i].num<0)
a[i].num = -a[i].num-1;
a[i].dis = i;//记录下位置
}
sort(a,a+n,cmp1);
if(n&1)
{
for(int i=0; i<n-1; i++)
{
a[i].num = -a[i].num-1;
}
sort(a,a+n,cmp2);
for(int i=0; i<n-1; i++)
{
cout<<a[i].num<<" ";;
}
cout<<a[n-1].num<<endl;;
}
else
{
for(int i=0; i<n; i++)
{
a[i].num = -a[i].num-1;
}
sort(a,a+n,cmp2);
for(int i=0; i<n; i++)
{
if(i==0)
cout<<a[i].num;
else
cout<<" "<<a[i].num;
}
cout<<endl;
}
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int aa[345678]
int main(){
int n;
int nn = 1;
int count;
cin>>n;
for(int i = 0;i<n;i++){
cin>>aa[i];
if(aa[i] >= 0) aa[i] = (-1)*aa[i]-1;
if(aa[i] < nn){
nn = aa[i];
count = 1;
}
}
if(n&1) aa[count] = (-1)*aa[count] - 1;
cout<<aa[0];
for(int i=1;i<=n;i++)
cout<<" "<<aa[i];
cout<<endl;
return 0;
}
#include<iostream>
#include<deque>
using namespace std;
const int N = 3e5+5;
typedef long long ll;
int n,m,maxx=0,num=0,ans[N];
deque<ll>q;
struct node {
int l,r;
}t[N];
void solve(){
while(1){
int x=q.front();q.pop_front();
int y=q.front();q.pop_front();
if(x==maxx){
q.push_front(y);
for(int i=1;i<=n-1;i++){
y=q.front();q.pop_front();
ans[i]=y;
}
break;
}
else {
num++;
t[num].l=x;t[num].r=y;
if(x>y){
q.push_front(x);
q.push_back(y);
}
else {
q.push_front(y);
q.push_back(x);
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) {
int x;
cin>>x;
maxx=max(maxx,x);
q.push_back(x);
}
solve();
for(int i=0;i<m;i++){
ll c;
cin>>c;
if(c<=num) cout<<t[c].l<<" "<<t[c].r<<endl;
else {
c-=num;
c%=(n-1);
if(c==0) c=n-1;
cout<<maxx<<" "<<ans[c]<<endl;
}
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,a,x,b,y;
cin>>n>>a>>x>>b>>y;
while(a!=x&&b!=y){
if(a==n) a=1;
else a++;
if(b==1)b=n;
else b--;
if(a==b){
cout<<"YES";
return 0;
}
}
cout<<"NO";
}
#include<bits/stdc++.h>
#define maxn 3000000+10
#define ll long long
using namespace std;
int a[maxn];
int b[maxn];
ll x,y,i,j,flag,v1,v2;
bool check(int n,int m){
for(int i=0;i<y;i++){
if(n != a[i] && n != b[i] && m != a[i] && m != b[i])
return false;
}
return true;
}
int main(){
while(cin>>x>>y){
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for(int i=0;i<y;i++)
cin>>a[i]>>b[i];
flag = a[0];
for(int i =1;i<y;i++){
if(flag != a[i] && flag != b[i]){
v1 = a[i];
v2 = b[i];
break;
}
}
if(check(flag,v1) || check(flag,v2)){
cout<<"YES"<<endl;
continue;
}
flag = b[0];
for(int i =1;i<y;i++){
if(flag != a[i] && flag != b[i]){
v1 = a[i];
v2 = b[i];
break;
}
}
if(check(flag,v1) || check(flag,v2)){
cout<<"YES"<<endl;
continue;
}
cout<<"NO"<<endl;
}
return 0;
}
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=3e5+10;
const int inf=0x3f3f3f3f;
void io(){
ios::sync_with_stdio(0);
cin.tie();
cout.tie();
}
int n,m,b;
int a[N];
bool check(int x)
{
int now=0;
for(int i=0;i<n;i++){
if(now<a[i]){
if(m-a[i]+now>x)now=a[i];
}else if(now>a[i]){
if(now-a[i]>x)return 0;
}
}
return 1;
}
int main()
{
io();
cin>>n>>m;
for(int i=0;i<n;i++) cin>>a[i];
int l=0,r=inf,mid;
while(l<r){
mid=(l+r)/2;
if(check(mid)){
r=mid;
}
else{
l=mid+1;
}
}
cout<<r<<endl;
return 0;
}
京公网安备 11010502036488号