西安电子科技大学第16届程序设计竞赛网络同步赛题目题解

2019-04-14 19:55发布

站内文章 / 模拟电子
11909 0 979
这套题目简单的是真简单，复杂的也是真不好写。尤其是后三道，奔溃啊。A-GRE(水题）#include #include #include #include using namespace std; mapm; void init() { m["zero"] = "ling"; m["one"] = "yi"; m["two"] = "er"; m["three"] = "san"; m["four"] = "si"; m["five"] = "wu"; m["six"] = "liu"; m["seven"] = "qi"; m["eight"] = "ba"; m["nine"] = "jiu"; m["ten"] = "shi"; } int main() { int t; cin>>t; init(); string str; while(t--) { cin>>str; cout<B-Words Game（水题）#include #include #include #include using namespace std; char str[1000000]; int vis[30]; int main() { while(~scanf("%s",str)) { memset(vis,0,sizeof(vis)); for(int i = 0; i < strlen(str); i++) { vis[str[i]-'a'] = 1; } int ans = 0; int n; scanf("%d ",&n); while(n--) { scanf("%s",&str); bool flag = true; int len = strlen(str); for(int i = 0; i < len; i++) { if(vis[str[i]-'a']==0) { flag = false; break; } } if(flag) { ans = max(ans,len); } } printf("%d ",ans); } return 0; }
C-Arch0n's interesting game（水题）#include #include #include #include using namespace std; int a[2600],b[5000000]; bool cmp(int n1,int n2) { return n1>n2; } int main() { int t,n,k; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&k); for(int i = 0; i < n; i++) { scanf("%d",&a[i]); } int cnt = 0; for(int i = 0; i < n; i++) { for(int j = i+1; j < n; j++) { b[cnt++] = min(a[i],a[j]); } } sort(b,b+cnt,cmp); printf("%d ",b[k-1]); } return 0; } D-另一个另一个简单游戏(水题)#include #include #include #include using namespace std; int arr[1000]; int main() { int n,t; scanf("%d",&t); while(t--) { scanf("%d",&n); long long sum = 0; for(int i = 0; i < n; i++) { scanf("%d",&arr[i]); sum += arr[i]; } printf("%d ",sum/n); } return 0; }
E-Xiedly And His Password/********************* Date 2018/4/22 Author Ms. Wen 解题思路： 动态规划，dp[i][j]用来代表以i处字符为结尾的值模 3后为j的值的个数。有一点，不知道为什么，直接用 strlen求字符串长度提交后，就是一直出错，拿一个 变量承接一下就没问题了。 ****************************/ #include #include #include using namespace std; typedef long long ll; const int maxn = 1e6+10; char str[maxn]; ll dp[maxn][4]; int main() { while(~scanf("%s",str)) { ll ans = 0; dp[0][0] = dp[0][1] = dp[0][2] = 0; if(str[0]=='0') { dp[0][0] = 1; ans++; } else { dp[0][1] = 1; } int len = strlen(str); for(int i = 1; i < len; i++) { if(str[i]=='0') { dp[i][0] = dp[i-1][0]+1; dp[i][2] = dp[i-1][1]; dp[i][1] = dp[i-1][2]; } else { dp[i][1] = dp[i-1][0]+1; dp[i][0] = dp[i-1][1]; dp[i][2] = dp[i-1][2]; } ans += dp[i][0]; } printf("%lld ",ans); } return 0; }
F-Operating System/******************** Date 2018/4/21 Author Ms. Wen 解题思路：这个题目属于计算机组成原理中的一个经典问题，遇到需要的东西 先到内存找，内存有，则命中，否则看内存是否满，未满，将内容从外存装入 内存，否则需要一定的替换算法去适当的替换内存中的某块。本题难点在于： 替换策略的设计。 基本思路：使用数组vis标记某编号的内容是否在内存中，如果在，不必考虑。 如果不再，则看cnt变量的值，cnt代表当前内存中被占了多少块，如果cnt #include #include #include using namespace std; const int maxn = 50010; int n,m,q; int vis[maxn]; int arr[maxn]; vectorv[maxn]; int main() { while(~scanf("%d%d%d",&n,&m,&q)) { for(int i = 0; i <= m; i++) { v[i].clear(); } int cnt=0,ans=0; memset(vis,0,sizeof(vis)); for(int i = 1; i <= q; i++) { scanf("%d",&arr[i]); if(vis[arr[i]]==0) { vis[arr[i]] = 1; v[0].push_back(arr[i]); } } for(int i = q; i > 0; i--) { v[arr[i]].push_back(i); //倒着压进时间 } memset(vis,0,sizeof(vis)); for(int i = 1; i <= q; i++) { int x = arr[i]; //内存中已经存在，不考虑 if(vis[x]==1) continue; if(cnt
G-小国的复仇#include #include #include using namespace std; const int maxn = 1e6+10; const int inf = 0x3f3f3f3f; int ans[maxn]; int prime[maxn]; void init() { memset(prime,0,sizeof(prime)); ans[1] = 0; for(int i = 2; i <= 1e6; i++) { if(prime[i]==0) { ans[i] = i-1; for(int j = 2*i; j <= 1e6; j+=i) { prime[j] = 1; int tmp = j; while(tmp%i==0) { ans[j] += ans[i]; tmp = tmp/i; } } } } } int main() { int n,t; init(); scanf("%d",&t); while(t--) { scanf("%d",&n); printf("%d ",ans[n]); } return 0; }
H-敬老师的手环II
I-Tr0y And His Startup/** 假如L,R范围遭到流量袭击。则对于L,R中的任意一个假设为i。 其最终导入第三方服务其的流量是：Sum(x[i],x[i]+1,..,C-1,C) 然后用等差数列求和：(x[i]+C)*(C-x[i]+1) / 2. (x[i]+C)*(C-x[i]+1) = C*(C+1) - x[i]*(x[i]-1); 因为i属于【L,R】。所以答案为(C*(C+1)*(R-L+1)-Sum((x[L]*(x[L]-1))+...(x[R]*(x[R]-1))))/(2*C); 所以只需要用线段树维护，Sum的值即可。 */ #include #include #include #define lchild left,mid,root<<1 #define rchild mid+1,right,root<<1|1 using namespace std; typedef long long LL; const int maxn = 1e5+10; const int mod = 1e9+7; LL x[maxn<<2],lazy[maxn<<2],sum[maxn<<2]; //更新当前节点的值。 void push_up(int root) { x[root] = x[root<<1] + x[root<<1|1]; sum[root] = sum[root<<1] + sum[root<<1|1]; } //下推标记 void push_down(int left,int right,int root) { if(lazy[root]) { int lroot = root<<1; int rroot = root<<1|1; int mid = (left+right)/2; //下推标记到左孩子。 sum[lroot] = sum[lroot] + 2*lazy[root]*x[lroot] + lazy[root]*(lazy[root]-1)*(mid-left+1); x[lroot] = x[lroot] + lazy[root]*(mid-left+1); lazy[lroot] += lazy[root]; //下推标记到右孩子。 sum[rroot] = sum[rroot] + 2*lazy[root]*x[rroot] + lazy[root]*(lazy[root]-1)*(right-mid); x[rroot] = x[rroot] + lazy[root]*(right-mid); lazy[rroot] += lazy[root]; //释放根节点的标记。 lazy[root] = 0; } } //构建线段树 void build(int left,int right,int root) { lazy[root] = x[root] = sum[root] = 0; if(left == right) { scanf("%lld",&x[root]); sum[root] = x[root]*(x[root]-1); return; } int mid = (left+right)/2; build(lchild); build(rchild); push_up(root); } //查询和值。 LL query(int L,int R,int left,int right,int root) { if(L<=left && right<=R) { return sum[root]; } push_down(left,right,root); int mid = (left+right)/2; LL ans = 0; if(L<=mid) ans += query(L,R,lchild); if(R>mid) ans += query(L,R,rchild); return ans; } //给L到R内每个x[i]加add。 void update(int L,int R,int add,int left,int right,int root) { if(L<=left && right<=R) { sum[root] = sum[root] + 2*add*x[root] + (LL)add*(add-1)*(right-left+1); x[root] = x[root] + (LL)add*(right-left+1); lazy[root] += add; return; } push_down(left,right,root); int mid = (left+right)/2; if(L<=mid) update(L,R,add,lchild); if(R>mid) update(L,R,add,rchild); push_up(root); } //用整数快速幂求乘法逆元。 LL qucikPow(LL n,LL k) { LL ans,res; ans = 1; res = n; while(k) { if(k&1) { ans = ans*res%mod; } k = k/2; res = res*res%mod; } return ans; } int main() { int n,c,q; while(~scanf("%d%d%d",&n,&c,&q)) { build(1,n,1); //因为mod是素数，所以可以用小费马定理求2*c模mod的乘法逆元。 LL tmp = qucikPow((LL)2*c,mod-2); int l,r,add; while(q--) { scanf("%d%d%d",&l,&r,&add); LL ans = query(l,r,1,n,1); LL C = c; ans = ((C*C%mod+C)%mod)*(r-l+1)%mod - ans; ans = ans%mod; ans = (ans+mod)%mod*tmp%mod; update(l,r,add,1,n,1); printf("%lld ",ans); } } return 0; }J-Database/******************************* Author Ms.Wen Date 2018/4/25 解题思路： 就是模拟执行sql语句的过程，按照操作进行模拟，思路是不好讲的。 这个题目写了5个小时。疯了，题目意思很简单，模拟过程很复杂啊。奔溃。 变量含义： t[][][]:三维数组用来存放表。t就代表数据库 id:用来给表进行编号，这样可以吧表名通过map映射成表编号。 arr:用来给某个表中的列进行编号，这样可以通过map把列名映射成编号。 num:用来记录某个表中的记录条数。 table:用来从表名映射成表编号。 m:用来从列名映射成列编号。 ********************************/ #include #include #include #include #include #include using namespace std; int t[6][6][120]; int id,arr[10],num[10]; maptable; //映射表名。 mapm[7]; //映射某表的列名。 sets; //初始化 void init() { id = 0; memset(t,0,sizeof(t)); memset(arr,0,sizeof(arr)); memset(num,0,sizeof(num)); for(int i = 0; i < 5; i++) { m[i].clear(); } } //建表函数 void createTable(string sql) { int pos; string tName=""; int len = sql.length(); //求表名 for(int i = 13; i < len; i++) { if(sql[i]=='(') { pos = i+1; break; } else { tName += sql[i]; } } table[tName] = id++; string colName=""; //列名 int tid = table[tName]; //给列进行编号。 for(int i = pos; i < len; i++) { if(sql[i]==';') break; if(sql[i]==' ') { colName = ""; } else if(sql[i]==','||sql[i]==')') { m[tid][colName] = arr[tid]; arr[tid]++; } else { colName += sql[i]; } } } //更新表的函数。 void updateTable(string sql) { string colName[10]; int value[10]; int cnt = 0; string tName=""; int pos; int len = sql.length(); //求表名 for(int i = 12; i < len; i++) { if(sql[i]=='(') { pos = i+1; break; } else { tName += sql[i]; } } int id = table[tName]; //求表的编号。 //求插入数据的列名 string cName = ""; for(int i = pos; i < len; i++) { if(sql[i]==')') { colName[cnt++] = cName; pos = i + 9; break; } else if(sql[i]==',') { colName[cnt++] = cName; } else if(sql[i]==' ') { cName = ""; } else { cName += sql[i]; } } int n = 0; cnt = 0; //求插入的值。 for(int i = pos; i < len; i++) { if(sql[i]==')') { value[cnt++] = n; break; } else if(sql[i]==',') { value[cnt++] = n; } else if(sql[i]==' ') { n = 0; } else { n = n*10 + (sql[i]-'0'); } } int row = num[id]; int colID; //插入数据 for(int i = 0; i < cnt; i++) { colID = m[id][colName[i]]; t[id][colID][row] = value[i]; } num[id]++; //表的记录数加1. } //第一种查询。 void query1(string sql,bool flag) { int colID[10]; int cnt = 0; string tName = ""; int len = sql.length(); int pos = sql.find("from"); sql[pos-1] = ','; //求表名 for(int i = pos+5; i < len; i++) { if(sql[i]==';') { break; } else { tName += sql[i]; } } int id = table[tName]; //求表号 string colName = ""; //求表头名称 for(int i = 7; i < pos; i++) { if(sql[i]==',') { colID[cnt++] = m[id][colName]; } else if(sql[i]==' ') { colName = ""; } else { colName += sql[i]; } } //代表是第三种查询语句。 if(flag) { int row = num[id]; for(int i = 0; i < row; i++) { for(int j = 0; j < cnt; j++) { if(j != 0) { printf(" "); } printf("%d",t[id][colID[j]][i]); } printf(" "); } printf(" "); } else { //说明是第四种查询的嵌套查询。 int row = num[id]; int col = m[id][colName]; s.clear(); for(int i = 0; i < row; i++) { s.insert(t[id][col][i]); } } } void query2(string sql,bool flag) { int pos = sql.find("from"); //求单词from的第一次出现的位置 int len = sql.length(); sql[pos-1] = ','; string colName[10]; int cnt = 0; string cName = ""; for(int i = 7; i < pos; i++) { if(sql[i]==',') { colName[cnt++] = cName; } else if(sql[i]==' ') { cName = ""; } else { cName += sql[i]; } } string tName = ""; for(int i = pos+5; i < len; i++) { if(sql[i]==' ') { pos = i; break; } tName += sql[i]; } cName = ""; for(int i = pos+7; i < len; i++) { if(sql[i]==' ') { pos = i; break; } cName += sql[i]; } string subsql; //求嵌套的子sql语句。 for(int i = pos+4; i < len; i++) { subsql += sql[i]; } //cout<tmpSet; int tid = table[tName]; //求表编号 int row = num[tid]; int col = m[tid][cName]; for(int i = 0; i < row; i++) { if(s.count(t[tid][col][i])) { for(int j = 0; j < cnt; j++) { int x = m[tid][colName[j]]; tmpSet.insert(t[tid][x][i]); } } } s.clear(); s = tmpSet; } else { int tid = table[tName]; int row = num[tid]; int col = m[tid][cName]; for(int i = 0; i < row; i++) { if(s.count(t[tid][col][i])) { for(int j = 0; j < cnt; j++) { int x = m[tid][colName[j]]; if(j != 0) { printf(" "); } printf("%d",t[tid][x][i]); } printf(" "); } } printf(" "); } } int main() { init(); string sql; while(getline(cin,sql)) { //表示该sql语句是建表操作。 if(sql.find("create")!=string::npos) { createTable(sql); } else if(sql.find("insert")!=string::npos) { updateTable(sql); } else if(sql.find("in")!=string::npos) { query2(sql,true); } else { query1(sql,true); } } return 0; } /* create table wussy(c1, c2, c3); insert into wussy(c1, c2) values(1, 2); select c1, c2, c3 from wussy; insert into wussy(c1, c2, c3) values(4, 5, 6); create table vampireweekend(c1, c2); insert into vampireweekend(c1) values(1); select c1, c2, c3 from wussy; select c1, c2 from wussy where c1 in select c1 from vampireweekend; */

热门文章