An abandoned sentiment from past

水题

#include<bits/stdc++.h>

using namespace std;

int a[300],b[300],n,k;
bool cmp(int a,int b)
{
return a>b;
}
int main()
{//freopen("t.txt","r",stdin);
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
for(int i=0;i<k;i++) scanf("%d",&b[i]);
sort(b,b+k,cmp );
for(int i=0,j=0;i<n&&j<k;i++)
{
if(a[i]==0)a[i]=b[j++];
}
for(int i=1;i<n;i++)
if(a[i]<=a[i-1]){printf("YES\n");return 0;}
printf("NO\n");
return 0;
}

An express train to reveries

水题

#include<bits/stdc++.h>

using namespace std;
const int N=2000;
int a[N],b[N],ans[N],color[N],n,vis[N]; int main()
{//freopen("t.txt","r",stdin);
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
for(int i=0;i<n;i++)scanf("%d",&b[i]);
int sum=0;
vector<int>ad;
ad.clear();
for(int i=0;i<n;i++)
if(a[i]==b[i])ans[i]=a[i],sum++,color[a[i]]++;
else ad.push_back(i);
vector<int>numa;
numa.clear();
for(int i=1;i<=n;i++)
if(color[i]==0)numa.push_back(i);
if(sum==n-1)
{
ans[ad[0]]=numa[(int)(numa.size()-1)];
}
else
{
if((a[ad[0]]==numa[0]&&b[ad[1]]==numa[1])||(b[ad[0]]==numa[0]&&a[ad[1]]==numa[1]))
{
ans[ad[0]]=numa[0];
ans[ad[1]]=numa[1];
}
else
{
ans[ad[1]]=numa[0];
ans[ad[0]]=numa[1];
}
}
for(int i=0;i<n-1;i++)
printf("%d ",ans[i]);
printf("%d\n",ans[n-1]);
return 0;
}

An impassioned circulation of affection

水题

#include<bits/stdc++.h>

using namespace std;

int dp[26][1510][1510],maxx[26][1510],ti[26][1510],n,q;
char ss[1510];
int main()
{//freopen("t.txt","r",stdin);
scanf("%d",&n);
scanf("%s",&ss);
for(int i=0;i<26;i++)
for(int j=0;j<n;j++)
{
int k=j;
while(k<n&&ss[k]==char(i+'a'))ti[i][j]++,k++;
}
for(int i=0;i<26;i++)
{
for(int j=0;j<n;j++)
{
for(int k=1;j+k<=n;k++)
{
if(dp[i][j][k-1]>=n){dp[i][j][k]=n;maxx[i][k]=max(maxx[i][k],dp[i][j][k]);continue;}
dp[i][j][k]=dp[i][j][k-1]+ti[i][min(n,j+dp[i][j][k-1])]+1+ti[i][min(n,j+dp[i][j][k-1]+ti[i][j+dp[i][j][k-1]]+1)];
if(dp[i][j][k]>n)dp[i][j][k]=n;
maxx[i][k]=max(maxx[i][k],dp[i][j][k]);
} }
}
//memset(dp,0,sizeof(dp));
scanf("%d",&q);
for(int i=0;i<q;i++)
{
char c;int jk;
getchar();
scanf("%d %c",&jk,&c);
int num=c-'a';
printf("%d\n",min(n,maxx[num][jk]));
}
return 0;
}

An overnight dance in discotheque

比较难的一道贪心题

可以证明 只要把最底层的圆扔到另一个半场 就达到了最优态

为什么呢?

在这个状态下无论我们怎么移动 都无法让答案变好。

简单证明一下:

我们可以把任意几个圆(顺序无关)扔到底层圆上,

这几个圆组成的覆盖,对某些面积(sb)进行了偶数次覆盖,对某些面积(sa)进行了奇数次覆盖。

而被覆盖的最底层圆,所有的面积都被奇数次(1次)覆盖,而偶数次的覆盖无法改变奇偶性,

奇数次的覆盖会将原本所有的奇数次覆盖变成偶数次覆盖(同时将偶数次覆盖变成奇数次)。

所以我们想要移动的这些圆无论处在什么位置 都比放在底层圆上对答案贡献大 

所以往单独在另一半场的底层圆(最大圆)移动任何圆的集合都不会让答案变好。

而所有的状态都可以从这个状态移动得到!

代码很简单(我这个蒟蒻想了半天DP方程 然而 O(n)贪心)

#include <bits/stdc++.h>
using namespace std; typedef long long LL; const long double pi = 3.14159265358979; #define N 100010 int x[N], y[N], r[N], dep[N], n; LL dist(int x, int y){ return 1ll * x * x + 1ll * y * y; } int main(){ ///freopen("in.txt", "r", stdin); scanf("%d", &n); for(int i = 1; i <= n; i ++){
scanf("%d %d %d", x + i, y + i, r + i);
} for(int i = 1; i <= n; i ++){
for(int j = 1; j <= n; j ++)if(r[j] > r[i]) {
if( dist( x[i] - x[j], y[i] - y[j]) <= 1ll * r[j] * r[j] ){
dep[i] ++;
}
}
} LL ans = 0; for(int i = 1; i <= n; i ++){
if(dep[i] == 0) ans += 1ll * r[i] * r[i];
else if(dep[i] & 1) ans += 1ll * r[i] * r[i];
else ans -= 1ll * r[i] * r[i];
} long double res = pi * ans; printf("%.10lf\n", (double) res); }

  

An unavoidable detour for home

非常具有技巧性的一道计数题

题目给定一个图的某些性质,要求我们构造一个层次图。每个点要么连接2个点要么连接3个点。

求不同的构图方法数量。

我们通过分层来计数。

solve(i,f)表示解决a[i]之后的序列答案,且第一层有f个元素。

connect(two,three,after)表示对于当前层次,有two个节点需连接2个节点,有three个节点要连接3个点,且构图后有after个可连接位(即下一层需要after个节点)

剩下的看代码吧 关键地方注释了 connect函数的转移非常有趣

#include <bits/stdc++.h>
using namespace std;
using LL=long long;
#define f(i,n) for(LL i=0;i<(n);i++) const LL M=1e9+7; LL n,d[50],cn[51][51][51],sl[51][51],n3[51]; LL connect(LL twos, LL threes, LL after){
if(twos<0||threes<0) return 0;
LL &cur=cn[twos][threes][after];
if(cur!=-1) return cur;
if(after) return cur=(twos*connect(twos-1,threes,after-1)%M//拿出一个two
+threes*connect(twos+1,threes-1,after-1)%M)%M;//拿出一个three 向下有一个空位 相当于增加了一个two
if(twos) return cur=((twos-1)*connect(twos-2, threes, after)%M//选出一对two互相连接
+threes*connect(twos,threes-1,after)%M)%M;//选出一个three和一个two连接后变成一个two
if(!threes) return 1;
return cur=((threes-1)*(threes-2)/2)*connect(2,threes-3,0)%M;//选出三个three后相当于增加了2个two } LL solve(LL i, LL f){
if(i+f>n) return 0;
if(i==n) return f==0;
if(f==0) return 0;
LL &cur=sl[i][f];
if(~cur) return cur;
LL r=0, threes=n3[i+f]-n3[i], twos=f-threes;
for(LL cl=0;cl<=n-(i+f);cl++)
r = (r+connect(twos, threes, cl)*solve(i+f,cl)%M)%M;
return cur=r;
} main(){freopen("t.txt","r",stdin);
ios::sync_with_stdio(0),cin.tie(0);
memset(cn,-1,sizeof(cn));
memset(sl,-1,sizeof(sl));
cin>>n;
f(i,n){
cin>>d[i];
n3[i+1]=n3[i]+(d[i]==3);
}
cout<<solve(1,d[0])<<'\n';
}

  

俩小时做了三道水题 还被Hack了一道 该拿什么拯救我的coding? 我这么菜可怎么办??

最新文章

  1. MySQL——保证数据的完整性
  2. 自定义view中错误:No resource identifier found for attribute X in package X
  3. Oracle数据创建表空间
  4. 【转】解决:fatal error C1083: 无法打开预编译头文件
  5. centos7 安装教程
  6. call &amp; apply
  7. Oracle DB 自动管理共享内存
  8. 错误记录--关于foreach,集合已修改;可能无法执行枚举操作
  9. CSS3 布局
  10. C++函数传值调用
  11. Visual Studio 2010 单元测试--运行测试并查看代码覆盖率
  12. 实现点击后创建div,若对div2秒无操作则将div隐藏,鼠标移上div让它不隐藏,移出div超过两秒则div隐藏
  13. datagridview 添加数据库数据
  14. css之absolute温习
  15. SSH File Transfer遇到错误"too many authentication failures for root".A protocol error was detected......
  16. maven 标签classifier 研究一下
  17. w3c JS测试
  18. Android之greenDao,一个orm的使用
  19. libsvm java版本使用心得(转)
  20. Java编程模板

热门文章

  1. 如何解决安装istio后istioctl命令每次使用都需要重新配置路径
  2. bzoj 3786 星系探索 dfs+splay
  3. for-else和wihle-else组合用法
  4. Intersecting Lines--POJ1269(判断两条直线的关系 &amp;&amp; 求两条直线的交点)
  5. BCD工具类(8421)
  6. MongoDB学习day09--Mongoose数据校验
  7. 如何解决XML文件中的警告提示“No grammar constraints (DTD or XML Schema) referenced in the document.”
  8. VC++如何折叠代码
  9. Native进程之Trace原理(转)——可直接输出某进程的栈帧——debuggerd
  10. Cocos2d-x 3.1.1 学习日志12--一Cocos2dx3.1.1移植到Android平台的方法(最实用最有效的!!)