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;
}
原文地址:http://www.cnblogs.com/aitejiu/p/16837792.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性