「CF549X」Looksery Cup 2015
A. Face Detection
模拟
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define mod 1000000007 #define ll long long using namespace std; int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,m,ans; char a[105][105]; map<char,int>mp; bool check(int x,int y) { mp.clear(); mp[a[x][y]]++;mp[a[x+1][y+1]]++; mp[a[x+1][y]]++;mp[a[x][y+1]]++; if(!mp['f'])return 0; if(!mp['a'])return 0; if(!mp['c'])return 0; if(!mp['e'])return 0; return 1; } int main() { n=read();m=read(); for(int i=1;i<=n;i++) scanf("%s",a[i]+1); for(int i=1;i+1<=n;i++) for(int j=1;j+1<=m;j++) if(check(i,j))ans++; printf("%d\n",ans); return 0; } |
B. Looksery Party
如果当前每个人还需要的信息数都非0，则已构造完
否则，找出为0的那个人，让其发一次信息（这个人之后一定<0）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define mod 1000000007 #define ll long long using namespace std; int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,b[105]; string a[105]; vector<int>ans; int main() { n=read(); for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++)b[i]=read(); bool flag=1; while(flag) { flag=0; for(int i=1;i<=n;i++) if(!b[i]) { flag=1; for(int j=1;j<=n;j++) if(a[i][j-1]=='1') b[j]--; ans.push_back(i); } } printf("%lu\n",ans.size()); for(int i=0;i<ans.size();i++) printf("%d\n",ans[i]); return 0; } |
C.The Game Of Parity
如果奇数和偶数城市都足够多，那么最后一个操作的人一定能将局面变成他想要的
否则就考虑某一方想将奇数或偶数的城市先取完
还要特判一下n=K的情况
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define mod 1000000007 #define ll long long using namespace std; int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,K; int A,B,a,b; string t1="Stannis",t2="Daenerys",ans; int main() { n=read();K=read();K=n-K; for(int i=1;i<=n;i++) { int x=read(); if(x&1)A++; else B++; } if(K==0) { if(A&1)cout<<t1<<endl; else cout<<t2<<endl; return 0; } if(K&1) { if(K/2>=A)ans=t2; else if(K/2>=B&&!((n-K)&1))ans=t2; else ans=t1; } else { if((K+1)/2>=B&&(n-K)&1)ans=t1; else ans=t2; } cout<<ans<<endl; return 0; } |
D. Haar Features
考虑(n,m)，它只能做(n,m)变换得到
所以从右下角开始，贪心+暴力即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define mod 1000000007 #define ll long long using namespace std; int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,m,ans; char a[105][105]; int b[105][105]; void solve(int x,int y,int val) { if(!val)return; ans++; for(int i=1;i<=x;i++) for(int j=1;j<=y;j++) b[i][j]+=val; } int main() { n=read();m=read(); for(int i=1;i<=n;i++) scanf("%s",a[i]+1); if(a[n][m]=='B')solve(n,m,1); else solve(n,m,-1); for(int i=n;i;i--) for(int j=m;j;j--) if(a[i][j]=='B') solve(i,j,1-b[i][j]); else if(a[i][j]=='W') solve(i,j,-1-b[i][j]); printf("%d\n",ans); return 0; } |
G. Happy Line
将所有人按照其钱数+所处位置进行排序
得出的序列就是最终序列
再依次计算每个人最终钱数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define mod 1000000007 #define ll long long using namespace std; int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,ans[200005]; struct data{ int val,id; }a[200005]; bool operator<(data a,data b) { return a.val+a.id<b.val+b.id; } int main() { n=read(); for(int i=1;i<=n;i++)a[i].val=read(),a[i].id=i; sort(a+1,a+n+1); for(int i=1;i<=n;i++)ans[i]=a[i].val-(i-a[i].id); for(int i=1;i<=n;i++) if(ans[i]<ans[i-1]) { puts(":("); return 0; } for(int i=1;i<=n;i++) printf("%d ",ans[i]); return 0; } |
H. Degenerate Matrix
二分答案，就能得出a*d，b*c的区间，判区间是否重合
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define mod 1000000007 #define ll long long using namespace std; int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } double p[5]; double min(double a,double b,double c,double d) { return min(a,min(b,min(c,d))); } double max(double a,double b,double c,double d) { return max(a,max(b,max(c,d))); } bool check(double mid) { double l1,r1,l2,r2; double a=p[1]-mid,b=p[1]+mid,c=p[4]-mid,d=p[4]+mid; l1=min(a*c,a*d,b*c,b*d); r1=max(a*c,a*d,b*c,b*d); a=p[2]-mid,b=p[2]+mid,c=p[3]-mid,d=p[3]+mid; l2=min(a*c,a*d,b*c,b*d); r2=max(a*c,a*d,b*c,b*d); return (l2<=l1&&l1<=r2)||(l2<=r1&&r1<=r2)||(l1<=l2&&l2<=r1)||(l1<=r2&&r2<=r1); } int main() { for(int i=1;i<=4;i++)p[i]=read(); double l=0,r=1000000000; for(int i=1;i<=100;i++) { double mid=(l+r)/2; if(check(mid))r=mid; else l=mid; } printf("%.10lf",l); return 0; } |
计数器 9320844
OI 课件=>
OI 课件=>
黄学长怎么看H题的O(1)方法？
请问是什么方法
实在是不知道应该如何证明……
最早出现在这:http://codeforces.com/blog/entry/18363?#comment-233514
现在已经遍地了吧……
O(1)方法貌似真的有。。。
貌似可以证明最优解的A-B矩阵中，四个元素的绝对值一定相等。
是呀评论区有证出来的可是然后呢……
每个数要是修改的话，那么一定是加或减，一共16种情况，每种情况解个方程就行了。
由于有绝对值……就没有那么多种情况了……
不过我好像是明白了:)谢啦