Educational Codeforces Round 1

C. Nearest vectors

题目大意

给出n个向量，求出其中夹角最小的两个向量。

分析

求出所有向量与x轴的夹角，然后排序，两两比较夹角。

AC_code

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
long  double Pi=acos(-1);
struct node{
	int x,y,id;
	long double a;
}p[100005];
bool cmp1(node a,node b){
	return a.a<b.a;
}
int n,ans1,ans2;
long double ans;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&p[i].x,&p[i].y);
		p[i].a=atan2(p[i].y,p[i].x);
		if(p[i].a<0)p[i].a+=2*Pi;
		p[i].id=i;
	}
	sort(p+1,p+n+1,cmp1);
	ans=p[1].a-p[n].a+2*Pi;
	ans1=p[n].id;ans2=p[1].id;
	for(int i=2;i<=n;i++){
		if(p[i].a-p[i-1].a<ans){
			ans=p[i].a-p[i-1].a;
			ans1=p[i-1].id;
			ans2=p[i].id;
		}
	}
	printf("%d %d",ans1,ans2);
	return 0;
}

D. Igor In the Museum

分析

直接暴力扫描出每一个联通块，算出每一个联通块的周长，然后结束了。

AC_code

#include <bits/stdc++.h>
#define fi first    
#define se second    
#define endl '\n'
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
using ll = long long;
using namespace std;
const int N = 1e5 + 10,M = N*2;

int dx[4] = {1,-1,0,0},dy[4] = {0,0,1,-1}   ;

void solve() {
    int n,m,k;
    cin>>n>>m>>k;
    vector<vector<char>> g(n+1,vector<char>(m+1));
    vector<vector<int>> id(n+1,vector<int>(m+1));
    vector<int> res;
    int cnt = 0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>g[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(g[i][j]!='*'&&!id[i][j])
            {
                cnt++;
                res.push_back(0);
                queue<pair<int,int>> q;
                id[i][j] = cnt;
                q.push({i,j});
                while(q.size())
                {
                    auto [x,y] = q.front();q.pop();
                    for(int i=0;i<4;i++)
                    {
                        int nx = x + dx[i],ny = y + dy[i];
                        if(nx<=0||nx>n||ny<=0||ny>m) continue;
                        if(g[nx][ny]=='*')
                        {
                            res[cnt-1]++;
                            continue;
                        }
                        if(id[nx][ny]) continue;
                        q.push({nx,ny});
                        id[nx][ny] = cnt;
                    }
                }
            }
    while(k--)
    {
        int x,y;cin>>x>>y;
        cout<<res[id[x][y]-1]<<'\n';
    }
}
 
int main() 
{
    ios;
    int T=1;
    // cin>>T;
 
    while(T -- ) {
        solve();
    }
 
    return 0;
}

E. Chocolate Bar

分析

状态定义为。

f[i][j][k]即为，从大小为ixj的矩阵中获得k块的代价。

转移方程为。

AC_code

#include <bits/stdc++.h>
#define fi first    
#define se second    
#define endl '\n'
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
using ll = long long;
using namespace std;
const int N = 35,M = N*2,inf = 0x3f3f3f3f;
   
int f[N][N][55];

int g(int n,int m,int p)
{
    if(n*m==p||!p) return 0;
    if(n>m) swap(n,m);
    if(f[n][m][p]) return f[n][m][p];
    int smin = inf;
    for(int i=1;i<=n/2;i++)
        for(int j=0;j<=p;j ++)
        {
            int ans = m*m + g(i,m,j) + g(n-i,m,p-j);
            smin = min(ans,smin);
        }
    for(int i=1;i<=m/2;i++)
        for(int j=0;j<=p;j++)
        {
            int ans = n*n + g(n,i,j) + g(n,m-i,p-j);
            smin = min(ans,smin);
        }
    return f[n][m][p] = smin;
}

void solve() {
    int n,m,k;cin>>n>>m>>k;
    cout<<g(n,m,k)<<'\n';
}
 
int main() 
{
    ios;
    int T=1;
    cin>>T;
 
    while(T -- ) {
        solve();
    }
 
    return 0;
}