题目连接：http://codeforces.com/contest/764
A. Taymyr is calling you
解题思路：
两个for循环，对一个数组进行操作，访问次数为2的数目为答案
时间复杂度：O(n)
空间复杂度：O(n)
代码如下：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
typedef vector<int> vi;
int dir[4][2]={{1,0},{0,-1},{-1,0},{0,1}};
const int N = 1e5+5;
int n,m,z;
string s;
int a[N];
int main()
{
cin >> n>>m>>z;
for(int i=0;i<=z;i+=n)
{
a[i]++;
}
for(int i=0;i<=z;i+=m)
{
a[i]++;
}
int re = 0;
for(int i=1;i<=z;i++)
{
if(a[i]>=2)
{
re++;
}
}
cout <<re<<endl;
return 0;
}
B. Timofey and cubes
解题思路：
根据交换次数的奇偶数来判断是否进行交换. 奇数交换，偶数不交换
时间复杂度：O(n)
空间复杂度：O(n)
代码如下：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
typedef vector<int> vi;
int dir[4][2]={{1,0},{0,-1},{-1,0},{0,1}};
const int N = 1e5+5;
int n,m,z;
string s;
int a[N*2];
int main()
{
cin >> n;
ll ct = 0;
rep(i,1,n)
{
cin >> a[i];
}
for(int i=1,j=n;i<=j;i++,j--)
{
if(ct%2==0)
{
int t = a[i];
a[i]= a[j];
a[j]= t;
}
ct++;
}
rep(i,1,n)
{
cout << a[i]<<" ";
}
cout <<endl;
return 0;
} C. Timofey and a tree
解题思路：
思路一：
先遍历有多少个联通块，然后根据联通块的颜色和数量，遍历各个边。
思路二：
先遍历有多少边两端点不同，然后根据边的数量来遍历，直到找到节点。
时间复杂度：O(n)
空间复杂度：O(n)
代码如下：
思路一代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
typedef vector<int> vi;
int dir[4][2]={{1,0},{0,-1},{-1,0},{0,1}};
const int N = 1e5+5;
bool book[N];
int n;
string s;
vi mpp[N];
int c[N];
int u,v,t;
int flag[N];
int ff = 0;
int ct1[N];
int ct2[N];
void dfs(int st,int col);
map<int,int> aa,bb;
map<int,int>::iterator it;
int main()
{
cin >> n;
rep(i,1,n-1)
{
cin >> u>>v;
mpp[u].push_back(v);
mpp[v].push_back(u);
}
rep(i,1,n)
{
cin >> c[i];
}
int le = 0;
rep(i,1,n)
{
if(book[i]==0)
{
aa[c[i]]++;
dfs(i,c[i]);
le++;
}
}
rep(i,1,n)
{
if(mpp[i].size()<le-1)
{
flag[i] = 1;
}
}
rep(i,1,n)
{
if(flag[i]==0)
{
ff = 0;
bb.clear();
for(int k=0;k<mpp[i].size();k++)
{
bb[c[mpp[i][k]]]++;
}
bb[c[i]]=1;
if(aa==bb)
{
cout << "YES"<<endl;
cout << i<<endl;
return 0;
}
}
}
cout << "NO"<<endl;
return 0;
}
void dfs(int st,int col)
{
for(int i=0;i<mpp[st].size();i++)
{
if(c[mpp[st][i]]==col&&book[mpp[st][i]]==0)
{
book[mpp[st][i]]=1;
dfs(mpp[st][i],col);
}
}
}思路二代码：
#include <iostream>
#include <stdio.h>
#define N 100005
using namespace std;
int u[N],v[N],vis[N],color[N],cnt;
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n-1;i++){
scanf("%d%d",&u[i],&v[i]);
}
for(int i=1;i<=n;i++){
scanf("%d",&color[i]);
}
for(int i=0;i<n-1;i++){
if(color[u[i]]!=color[v[i]]){
cnt++;
vis[u[i]]++;
vis[v[i]]++;
}
}
for(int i=1;i<=n;i++){
if(vis[i]==cnt){
printf("YES\n%d\n",i);
return 0;
}
}
printf("NO\n");
}D. Timofey and rectangles 思维题
解题思路：
因为矩形的边为奇数长度
根据四色定理，染色一定会成功。
(1)我们只看左下角坐标，如果两个数值都为奇数，那么右上角坐标一定两个都为偶数，所以所有左下标坐标为奇数的不会相交，可赋值为1。
(2)
如果x轴为偶数，可能与1的情况左右相邻赋值为2。
(3)
如果y轴为偶数，可能与1的情况左右相邻，赋值为3。
(4)
其余赋值为4。
时间复杂度：O(n)
空间复杂度：O(n)
代码如下：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
typedef vector<int> vi;
int dir[4][2]={{1,0},{0,-1},{-1,0},{0,1}};
const int N = 1e5+5;
int n;
int main()
{
int a,b,c,d;
cin >> n;
cout << "YES"<<endl;
while(n--)
{
cin >> a>> b>>c>>d;
if(a%2&&b%2)
{
cout << 1<<endl;
}
else if(a%2==0&&b%2)
{
cout << 2<<endl;
}
else if(a%2&&b%2==0)
{
cout << 3<<endl;
}
else
{
cout << 4<<endl;
}
}
return 0;
}