苏州大学ICPC集训队新生赛第二场
2024-09-07 01:50:45
A - Score
水
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
while(n--){
int sum=;
string s;
cin>>s;
int len=s.size();
int tmp=;
for(int i=;i<len;i++){
if(s[i]=='O')sum+=tmp,tmp++;
else {
sum+=tmp;
tmp=;
}
}
sum+=tmp;
cout<<sum<<endl;
}
return ;
}
B - Tetrahedron
题意:四面体,从D走n-1步回到D点,问你有多少种走法,数据量1e7;
标准错误解法:广搜:
#include<iostream>
#include<queue>
using namespace std;
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
#define per(i,j,k) for(int i=(int)k;i>=(int)j;i--)
#define pb push_back
#define pf push_front
#define fi first
#define se second 11
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef double db;
// const db PI=acos(-1.0);
const ll INF=0x3f3f3f3f3f3f3f3fLL;
const int inf=0x3f3f3f3f;//0x7fffffff;
const double eps=1e-;
const ll MOD=1e9+;
const int maxn=1e3+;
ll n,ans;
struct node{int id;ll step;node(int x,ll y){id=x,step=y;}};
void bfs(){
queue<node>Q;
Q.push(node(,));
while(!Q.empty()){
node tmp=Q.front();
Q.pop();
if(tmp.step==n&&tmp.id==){
ans++;
}
if(tmp.id==&&tmp.step<n){
int t=(tmp.step+)%MOD;
Q.push(node(,t));
Q.push(node(,t));
Q.push(node(,t));
}
if(tmp.id==&&tmp.step<n){
int t=(tmp.step+)%MOD;
Q.push(node(,t));
Q.push(node(,t));
Q.push(node(,t));
}
if(tmp.id==&&tmp.step<n){
int t=(tmp.step+)%MOD;
Q.push(node(,t));
Q.push(node(,t));
Q.push(node(,t)); } if(tmp.id==&&tmp.step<n){
int t=(tmp.step+)%MOD;
Q.push(node(,t));
Q.push(node(,t));
Q.push(node(,t));
}
}
}
int main(){
cin>>n;
ans=;
bfs();
cout<<ans<<endl;
// system("pause");
return ;
}
fyh正解:dp;
这个很像dp,定义状态: dp(i,j)为走i步,到了 j 点 ;
每走一步都受前面状态影响:转移方程为: dp[i][j]+=dp[i-1][k];
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
#define per(i,j,k) for(int i=(int)k;i>=(int)j;i--)
#define pb push_back
#define pf push_front
#define fi first
#define se second 11
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef double db;
// const db PI=acos(-1.0);
const ll INF=0x3f3f3f3f3f3f3f3fLL;
const int inf=0x3f3f3f3f;//0x7fffffff;
const double eps=1e-;
const ll MOD=1e9+;
const int maxn=1e7+;
int dp[maxn][];
int main(){
int n;
cin>>n;
dp[][]=;
dp[][]=;
dp[][]=;
dp[][]=;
for(int i=;i<=n;i++)
for(int j=;j<=;j++){
for(int k=;k<=;k++){
if(j==k)continue;
dp[i][j]+=dp[i-][k];
// else dp[i][j]=
dp[i][j]%=MOD;
}
}
cout<<dp[n][]<<endl;
return ;
}
G - Jumping Jack
题意:给你一个x 小于1e9;问你从0走到x要走几步;
解法:这题本来想广搜,问题和抓住那头牛很像,但数据量太大,搜索爆炸,本来想优化,但怎么搞呢?
正解:你想他 想左走向右走,在第n步,本来走 n+n+1,但现在变成了 -n+n+1,相差 2*n 步,这是个微调;
那你直接一直跳,超过的步数如果是偶数,就n/2步,是奇数肯定不能这样微调的,只能继续走。
和抓住这头牛 不一样,这题向左再向右是有策略的 ,可以微调的;
#include<bits/stdc++.h>
using namespace std;
int main(){
int x;
cin>>x;
if(x<)x=-x;
int sum=;
int i;
for(i=; ;i++){
sum+=i;
if(sum==x)break;
else if(sum>x&&(sum-x)%==)break; }
cout<<i<<endl;
return ;
}
D - Ehab and a 2-operation task
这题傻眼了:
题意:让你对一个序列进行n+1次操作。怎么把它变成严格单增的序列;
做法:先模1,这样全都清空为0,然后都变成2*n,一步步取余,最后就是单增得了;
但是为什么不是2n呢,手算一下就知道了,后面会重合;
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,k;
cin>>n;
for(int i=;i<=n;i++)scanf("%d",&k);
printf("%d\n",n+);
printf("2 %d 1\n",n);
printf("1 %d %d\n",n,*n);
for(int i=;i<n;i++){
printf("2 %d %d\n",i,*n-i);
} return ;
}
C - Permute Digits
题意:给你a,b,让你把a变成小于b的最大数。
解法:开始大模拟:
但一直wa,后来又mqf给了这样一组数据;3517 3503,
开始没有考虑取不到解的情况。
就是你一直取大于小于的,如果后面无解呢?只能回退,让前面的变小。
这点没考虑到。
然后模拟一直崩,有时间再来调一下。
错误解法:
#pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front
#define fi first
#define se second 11
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef double db;
const db PI=acos(-1.0);
const ll INF=0x3f3f3f3f3f3f3f3fLL;
const int inf=0x3f3f3f3f;//0x7fffffff;
const double eps=1e-;
const ll MOD=1e9+;
const int maxn=1e7+;
int vis[];
bool flag;
int find(int x){
for(int j=;j>=;j--){
if(!flag&&vis[j]>&&j<=x){
if(j<x)flag=;
vis[j]--;
return j;
} else if(flag&&vis[j]>){
vis[j]--;
return j; }
}
return -;
}
int main(){ flag=;
string sa,sb;
cin>>sa>>sb;
if(sa.size()<sb.size()){
sort(sa.begin(),sa.end());
int len=sa.size();
for(int i=len-;i>=;i--)//逆序输出
cout<<sa[i];
} else {
memset(vis,,sizeof vis);
// vector<int>ans;
int ans[];
int len=sa.size();
for(int i=;i<len;i++){
int tmp=sa[i]-'';
vis[tmp]++;
} len=sb.size();
int i;
for( i=;i<len;i++){
int t=sb[i]-'';
int tmp=find(t);
if(tmp!=-)ans[i]=tmp;
else { while(tmp==-){
i--;
vis[ans[i]]++;
t=sb[i]-''-;
tmp=find(t);
}
ans[i]=tmp;
vis[tmp]--;
flag=;
} }
// int p=0;
// while(ans[p]==0&&p!=len-1)p++; for(int i=;i<len;i++)
cout<<ans[i];
}
return ;
}
//
正确解法:用string里的大小比较,默认最小,然后每次从最高位开始找,能替换就替换掉。
如果替换后大于b,就退回来,确实很巧妙。
#include<bits/stdc++.h>
using namespace std;
int main(){
string t,a,b;
cin>>a>>b;
sort(a.begin(),a.end());
if(a.size()<b.size()){
reverse(a.begin(),a.end());
}
else {
int len=a.size();
int L,R;
for(L=;L<len;L++){
R=len-;
t=a;
while(L<R){
swap(a[L],a[R--]);
sort(a.begin()+L+,a.end());
if(a>b)a=t;
else break;
} } }
cout<<a<<endl;
return ;
}
英语吓得不轻;
#include<bits/stdc++.h>
using namespace std;
int main(){
int suma=,sumb=,oka=,okb=;
int n,t,x,y;
cin>>n;
while(n--){
cin>>t>>x>>y;
if(t==){
suma+=;
oka+=x;
}
else {
sumb+=;
okb+=x;
}
}
if(oka>=suma/)cout<<"LIVE"<<endl;
else cout<<"DEAD"<<endl;
if(okb>=sumb/)cout<<"LIVE"<<endl;
else cout<<"DEAD"<<endl; return ;
}
F - Squares
看清题意就好了,站在边上的不算属于这个空间;
#include<bits/stdc++.h>
using namespace std;
int a[];
int main(){
int n,k;
cin>>n>>k;
for(int i=;i<=n;i++)scanf("%d",&a[i]);
sort(a+,a++n);
if(k>n)cout<<"-1"<<endl;
else {
cout<<a[n-k+]<<" "<<a[n-k+]<<endl;
}
return ;
}
最新文章
- 了解screen对象的常用视图属性
- Xstream学习资料
- java实现单链表反转
- LeetCode130:Surrounded Regions
- jquery easyui datagrid使用参考
- URL路由规则实例
- java中保留几位小数
- jsPlumb开发入门教程(实现html5拖拽连线)
- cf B. Petya and Staircases
- scala写算法-List、Stream、以及剑指Offer里部分题目基于scala解法
- 实验-使用VisualVM或JConsole进行对程序进行性能分析
- 如何一步步在生产环境上部署django和vue
- python httplib和urllib的性能比较
- 关于C#中async/await中的异常处理(下)-(转载)
- Return array from functions in C++
- 使用JSP的fmt标签实现国际化支持
- bzoj3404
- 慕课网笔记之oracle开发利器-PL/SQL基础
- linux下创建virtualenv时指定python版本
- Android动态设置字体颜色
热门文章
- PDO 小知识
- Jquery设置完颜色后hover不生效的解决办法
- SICOM SOP
- Windows7 wampServer3.0.6 Mutillidae2.7.12
- leetcode142 Linked List Cycle II
- 16 SQL Mode
- POJ 3259:Wormholes bellman_ford判定负环
- GNS3 ProxyArp(查看路由器是否具有转发功能)
- express 配置 https 服务 ( 以阿里云服务器为例), 探索一周终于搞定
- 139. Word Break 以及 140.Word Break II