当前位置：网站首页>2022 Hangzhou Electric Multi-School 1st Game
2022 Hangzhou Electric Multi-School 1st Game
2022-08-05 03:24:00 【_zpf】
C.Backpack
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1024;
ll solve(){
int n,m;
cin>>n>>m;
vector<bitset<N>>dp(N);
// dp ijk 表示前i个物品,The total value is XORedj,总体积为k
//其中iThe dimensions of the representation are optimized away using rolling arrays
vector<pair<int,int>>v(N);
for( int i=0;i<n;i++){
cin>>v[i].first>>v[i].second;
}
dp[0][0]=1;
for( int i=0;i<n;i++){
vector<bitset<N>> ndp=dp;
for( int j=0;j<N;j++){
ndp[j]|=(dp[j^v[i].second]<<v[i].first);
}
dp=ndp;
}
for( int i=N-1;i>=0;i--){
if(dp[i][m]) return i;
}
return -1;
}
int main(){
int t;
cin>>t;
while(t--){
cout<<solve()<<"\n";
}
system("pause");
}
D.Ball
The meaning of the question is probably from a set of pointsSPick any three points,There are three distance values between these three points,If the median of the three distance values is a prime number,则答案加一.
首先,To determine prime numbers, use a prime number sieve.
If violence is used,枚举三个点,会时间超限.
正确做法是：
首先,枚举两个点,Calculate the line segment determined by all two points,Then sort by the length of the line segments,Use length ordering to reduce time complexity.
Traverse the entire sequence of line segments,Take the current line segment as the median,Left of the current line segment（The length is less than or equal to the current line segment）and take two line segments from the sequence on the right,form an answer.
需要注意的是,The three line segments need to have common endpoints,To maintain endpoints,Just use twobitset,A line segment endpoint that has been visited,The other represents line segment endpoints that have not been visited,The two sets are combined,然后统计1的数量即可.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200100;
vector<int>is_prime(N);
int solve(){
int n,m;
cin>>n>>m;
vector<pair<int,int>>v(n);
for( int i=0;i<n;i++){
cin>>v[i].first>>v[i].second;
}
vector<array<int,3>>vv;
for( int i=0;i<n;i++){
for( int j=i+1;j<n;j++){
vv.push_back({
abs(v[i].first-v[j].first)+abs(v[i].second-v[j].second),i,j});
}
}
sort(vv.begin(),vv.end());
vector<bitset<2000>>W(2000),B(2000);
//W[i][j]表示从i到jThe line segment has not been visited
//B[i][j]表示从i到jThe line segment has been visited
for( int i=0;i<2000;i++){
W[i].set();
}
int ans=0;
for( int i=0;i<vv.size();i++){
int x=vv[i][1],y=vv[i][2];
if(!is_prime[vv[i][0]]) {
ans+=(W[x]&B[y]).count()+(W[y]&B[x]).count();
}
W[x][y]=0;W[y][x]=0;
B[x][y]=1;B[y][x]=1;
}
return ans;
}
int main(){
is_prime[1]=1;
for( int i=2;i<N;i++){
if(is_prime[i]==0){
for( int j=i+i;j<N;j+=i){
is_prime[j]=1;
}
}
}
int t;
cin>>t;
while(t--){
cout<<solve()<<"\n";
}
system("pause");
}
H.Path
Use the layered graph method.
Build a layered graph with two layers,The first layer represents that the previous path to the point is not a special path,The second layer represents the previous path to this point is a special path.
If a normal path is read,Then add a path in the first layer and add a path to the first layer in the corresponding position of the second layer.If read in a special path,Then add a path leading to the second layer at the corresponding position of the second layer and add a path leading to the second layer at the corresponding position of the first layer.
除此之外,We also need to consider the direct problem after passing through the special path.对于这个问题,Because of the price0,我们只需要使用一个setMaintenance does not go straight to the point,If the current point is in the second layer of the graph,则遍历set中的所有点,Enqueue points that are not adjacent to the current point.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
void solve(){
const int inf=1e18;
int n,m,s,k;
cin>>n>>m>>s>>k;
vector<vector<pair<int,int>>>g(n+n+2);
auto add=[&](int x,int y,int w,int t){
if(t==0){
g[x].push_back({
y,w});
g[x+n].push_back({
y,w});
}
else {
g[x].push_back({
y+n,w});
g[x+n].push_back({
y+n,w});
}
};
for( int i=0;i<m;i++){
int x,y,w,t;
cin>>x>>y>>w>>t;
add(x,y,w,t);
}
set<int>unvis;
for( int i=1;i<=n;i++){
unvis.insert(i);
}
vector<int>dis(n+n+1,inf);
dis[s]=0;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
q.push({
0,s});
while(!q.empty()){
auto cur=q.top();
q.pop();
int d=cur.first,x=cur.second;
if(x>n){
set<int>adj;
for( auto it:g[x]){
if(it.first>n){
adj.insert(it.first);
adj.insert(it.first-n);
}
else {
adj.insert(it.first);
adj.insert(it.first+n);
}
if(dis[x]+it.second-k<dis[it.first]){
dis[it.first]=dis[x]+it.second-k;
q.push({
dis[it.first],it.first});
}
}
vector<int>temp;
for( auto it:unvis){
if(adj.count(it)) {
continue;
}
else if(dis[x]<dis[it]){
dis[it]=dis[x];
q.push({
dis[it],it});
}
temp.push_back(it);
}
for( auto it:temp){
unvis.erase(it);
}
}
else{
for( auto it:g[x]){
if(dis[x]+it.second<dis[it.first]){
dis[it.first]=dis[x]+it.second;
q.push({
dis[it.first],it.first});
}
}
}
}
for( int i=1;i<=n;i++){
int ans=min(dis[i],dis[i+n]);
if(ans==inf){
cout<<-1<<" ";
}
else cout<<ans<<" ";
}
cout<<"\n";
}
signed main(){
// FILE* file = freopen("out.txt", "w",stdout );
// FILE* f = freopen("1008.in", "r",stdin );
int t;
cin>>t;
while(t--){
solve();
}
system("pause");
}
I.Laser
易知,The entire radar ray range consists of four lines,Then the first point must be on one of the four lines.
- 首先,Check if all points are collinear with the first point,如果共线,直接返回yes
- If there is a point that is not collinear with the first point,Then these two points can discuss the center point of the entire radar radiation range,Just violently judge whether the center point meets the requirements.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
// #define x first
// #define y second
struct line
{
int a,b,c;
line(int a,int b,int c):a(a),b(b),c(c){
}
pair<int,int>cross(line l){
int d = this->a*l.b-l.a*this->b;
int x = (this->b*l.c-l.b*this->c)/d;
int y = (l.a*this->c-this->a*l.c)/d;
return {
x,y};
}
};
int parallel( line x,line y){
return x.a*y.b-x.b*y.a==0;
}
vector<line> get_line(pair<int,int>p){
vector<line>res;
//ax+by+c==0
res.push_back(line(0,1,-p.second));
res.push_back(line(1,0,-p.first));
res.push_back(line(1,1,-p.first-p.second));
res.push_back(line(1,-1,p.second-p.first));
return res;
}
int solve(){
int n;
cin>>n;
vector<pair<int,int>>v(n);
for( int i=0;i<n;i++){
cin>>v[i].first>>v[i].second;
// v[i].first*=2;v[i].second*=2;
}
auto collinear=[&](pair<int,int>a,pair<int,int>b)->int{
if(a.first==b.first||a.second==b.second||abs(a.first-b.first)==abs(a.second-b.second))
return true;
else
return false;
};
//Check if all points are summedv0共线
auto check1=[&]()->int{
for( int i=1;i<n;i++){
if(!collinear(v[0],v[i])){
return i;
}
}
return -1;//都和v0共线
};
int x=check1();
if(x==-1) return true;
auto good=[&](pair<int,int>p){
for( int i=0;i<n;i++){
if(!collinear(p,v[i])) return false;
}
return true;
};
//已知v0和x不共线,So discuss these two lines on which line
auto check2=[&]()->int{
auto xx=get_line(v[x]);
auto yy=get_line(v[0]);
for( auto it:xx){
for( auto itt:yy){
if(parallel(it,itt)) continue;
auto p=it.cross(itt);
if(good(p)) return true;
}
}
return false;
};
return check2();
}
int main(){
int t;
cin>>t;
while(t--){
if(solve()){
cout<<"YES"<<"\n";
}
else {
cout<<"NO"<<"\n";
}
}
system("pause");
}
K.Random
Every number left is expected to be0.5,Just take the inverse directly.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P = 1000000007;
using i64 = long long;
// assume -P <= x < 2P
int norm(int x) {
if (x < 0) {
x += P;
}
if (x >= P) {
x -= P;
}
return x;
}
template<class T>
T power(T a, int b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
struct Z {
int x;
Z(int x = 0) : x(norm(x)) {
}
int val() const {
return x;
}
Z operator-() const {
return Z(norm(P - x));
}
Z inv() const {
assert(x != 0);
return power(*this, P - 2);
}
Z &operator*=(const Z &rhs) {
x = ll(x) * rhs.x % P;
return *this;
}
Z &operator+=(const Z &rhs) {
x = norm(x + rhs.x);
return *this;
}
Z &operator-=(const Z &rhs) {
x = norm(x - rhs.x);
return *this;
}
Z &operator/=(const Z &rhs) {
return *this *= rhs.inv();
}
friend Z operator*(const Z &lhs, const Z &rhs) {
Z res = lhs;
res *= rhs;
return res;
}
friend Z operator+(const Z &lhs, const Z &rhs) {
Z res = lhs;
res += rhs;
return res;
}
friend Z operator-(const Z &lhs, const Z &rhs) {
Z res = lhs;
res -= rhs;
return res;
}
friend Z operator/(const Z &lhs, const Z &rhs) {
Z res = lhs;
res /= rhs;
return res;
}
};
int main(){
int t;
cin>>t;
while(t--){
int n,m;
scanf("%d%d",&n,&m);
if(n==m){
cout<<0<<"\n";
}
else {
cout<<(Z(1)/2*(n-m)).val()<<"\n";
}
}
system("pause");
}
L.Alice and Bob
0的数量为1时,is a must win.此外,for all states,若x的数量为n,Then the state can be equivalentn/2个x-1
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int solve(){
int n;
cin>>n;
vector<int>v(n+1);
for( int i=0;i<=n;i++){
cin>>v[i];
}
for( int i=n;i>0;i--){
v[i-1]+=v[i]/2;
}
if(v[0]) return true;
else return false;
}
int main(){
int t;
cin>>t;
while(t--){
if(!solve()){
cout<<"Bob"<<"\n";
}
else {
cout<<"Alice"<<"\n";
}
}
system("pause");
}
边栏推荐
- How to find all fields with empty data in sql
- Use SuperMap iDesktopX data migration tool to migrate ArcGIS data
- Use SuperMap iDesktopX data migration tool to migrate map documents and symbols
- public static
List asList(T... a) What is the prototype? - Use Unity to publish APP to Hololens2 without pit tutorial
- 2022-08-04 The sixth group, hidden from spring, study notes
- Beidou no. 3 short message terminal high slope in open-pit mine monitoring programme
- CPDA|How Operators Learn Data Analysis (SQL) from Negative Foundations
- 语法基础(变量、输入输出、表达式与顺序语句完成情况)
- The usage of try...catch and finally in js
猜你喜欢
![[Qixi Festival] Romantic Tanabata, code teaser.Turn love into a gorgeous three-dimensional scene and surprise her (him)!(send code)](/img/10/dafea90158adf9d43c4f025414fef7.png)
[Qixi Festival] Romantic Tanabata, code teaser.Turn love into a gorgeous three-dimensional scene and surprise her (him)!(send code)
dmp (dump) dump file
Matlab drawing 3
论治理与创新，2022 开放原子全球开源峰会 OpenAnolis 分论坛圆满落幕
Beidou no. 3 short message terminal high slope in open-pit mine monitoring programme
Use SuperMap iDesktopX data migration tool to migrate map documents and symbols
Simple description of linked list and simple implementation of code
21天学习挑战赛（2）图解设备树的使用
Kubernetes 网络入门
用Unity发布APP到Hololens2无坑教程
随机推荐
tree table lookup
你要的七夕文案，已为您整理好！
How to Add Category-Specific Widgets in WordPress
QT: The Magical QVarient
Object.defineProperty monitors data changes in real time and updates the page
语法基础(变量、输入输出、表达式与顺序语句)
Dynamic management of massive service instances
Use @Mapper to query the partition status of oracle and report an error
Beyond YOLO5-Face | YOLO-FaceV2 officially open source Trick+ academic point full
[Storage] Dawning Storage DS800-G35 ISCSI maps each LUN to the server
【软件测试】自动化测试之unittest框架
How to sort multiple fields and multiple values in sql statement
冰蝎V4.0攻击来袭，安全狗产品可全面检测
Tencent Cloud [Hiflow] New Era Automation Tool
论治理与创新，2022 开放原子全球开源峰会 OpenAnolis 分论坛圆满落幕
Summary of domestic environments supported by SuperMap
2022.8.4-----leetcode.1403
The usage of try...catch and finally in js
QT MV\MVC structure
How to find all fields with empty data in sql